首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode 25 Reverse Nodes in k-Group

Leetcode 25 Reverse Nodes in k-Group

作者头像
triplebee
发布2018-01-12 15:08:01
4900
发布2018-01-12 15:08:01
举报

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example, Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

将单链表按K个一组逆置。

思路是遍历链表,每遍历到K个就递归,返回值为当前一组的头节点,得到后面逆置的结果后,对本组进行逆置。

K<2和长度不足K的时候特判!

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) 
    {
        if(k<2) return head;  //k<2
        ListNode* p=head;
        int cnt=0;
        while(p!=NULL)
        {
            cnt++;
            if(cnt==k)
            {
                ListNode* q=head->next;
                head->next=reverseKGroup(p->next,k);
                for(int i=1;i<k;i++)
                {
                    ListNode* temp=q->next;
                    q->next=head;
                    head=q;
                    q=temp;
                }
                break;
            }
            p=p->next;
        }
        return cnt==k?p:head; //长度不足K
    }
};
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2016-09-02 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档