Leetcode 25 Reverse Nodes in k-Group

triplebee

发布于 2018-01-12 15:08:01

5330

发布于 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 删除

node.js