题目

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

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

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

Note:

Only constant extra memory is allowed.
You may not alter the values in the list's nodes, only nodes itself may be changed.

思路

先分析题目的几个要求：

每k个节点一组进行翻转，返回翻转之后的链表
如果节点总数不是k的整数倍，则剩余节点保留原有顺序
只能使用常数的额外空间
不能只是单纯改变节点的内部值，而是对节点进行交换

分析可知，题目要求实现两个功能，一个是如何实现每k个节点一组；一个是翻转节点。

每k个节点分组
- 循环：定义一个变量count记录走过的节点长度。如果count是k的整数倍，就进行翻转；如果不是，继续遍历节点。
- 递归：分别定义节点1（用于记录每个分组结束位置的下一个节点）和节点2（每个分组的第一个节点），递归将节点2到节点1之间的节点翻转。
翻转节点
- 头插法
- 记录节点法

这两个功能所用的方法可以自由组合。

思路1：头插法+递归

分组用递归完成：

定义节点lCur记录分组结束位置的下一个节点，通过k循环来找到每个lCur；利用节点head记录每个分组的开始位置。翻转从head到lCur之间的节点，完成一组节点的翻转，得到一组新的节点lHead。此时节点head已经到了分组的最后一位，从后面接上递归调用下一分组得到的新节点lHead，并返回新节点。

翻转用头插法完成（实现方法见Tips）：

头插法以链表1->2->3->4->5为例子，假设k=5，完成如下图过程：

思路2：记录节点法+循环

分组用循环完成，翻转用记录节点完成（实现方法见Tips）。

以链表1->2->3->4->5为例子，假设k=4，完成如下过程：

2->1->3->4->5

3->2->1->4->5

4->3->2->1->5

如上是4个一组的节点翻转，每行代表一次循环。

Tips

节点的翻转有两种方法

（1）头插法

新建一个虚拟节点dummy，并保证虚拟节点连接链表的头节点。每当遍历到一个节点时，就把它连接到虚拟节点的下一个节点（整个链表的头部）。定义pCur为当前要翻转的节点，过程如下：

//Step1：新建一个节点记录下一个要翻转的节点

ListNode* pNext = pCur->next;

 //Step2：将pCur置于整个节点的头部（即已经翻转好的节点的头部，完成翻转）

pCur->next = dummy->next;

//Step1：更新虚拟节点dummy的指向，使其指向链表的头节点

dummy->next = pCur;

//Step4：更新当前节点，将其置于下一个要翻转的节点

pCur = pNext;

翻转的过程如图所示（以要翻转的节点的值为3为例）：

（2）记录节点法

pCur表示当前要翻转的节点，pPre表示当前要翻转的前一个节点（也是已经完成翻转操作的最后一个节点），一次翻转过程（一次循环）如下：

// Step1：pPre连接下一个要翻转的节点

pPre->next = pCur->next;

// Step2：pCur节点连接已经翻转好的节点（翻转当前节点）

pCur->next = dummy->next;

// Step3：更改虚拟节点的连接，使它指向已经翻转好的节点

dummy->next = pCur;

// Step4：pCur指向下一个要翻转的节点

pCur = pPre->next;

翻转的过程如图2所示：

图2：记录节点翻转图解
#C++

思路1

/**

 * 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) {

        ListNode* lCur =head; //该节点用于记录每组节点结束后的下一个节点

        //循环找到每组结束的下一个节点

        for(int i= 0 ; i < k; i++){

            if(lCur == nullptr)

                return head;

            lCur = lCur->next;

        }

        ListNode* lHead = reverseOneGroup(head,lCur);

        head->next = reverseKGroup(lCur, k);

        return lHead;

    }

    /**

     * @Description:头插法实现一组节点内的翻转

     * lHead：当前一组节点的头节点

     * lTail：当前一组节点结束位置的下一个节点

     */

    ListNode* reverseOneGroup(ListNode* lHead, ListNode* lTail){

        ListNode* dummy = new ListNode(-1);

        ListNode* lCur = lHead;

        while(lCur != lTail){

            ListNode* lNext = lCur->next;

            lCur->next = dummy->next;

            dummy->next = lCur;

            lCur = lNext;

        }

        return dummy->next;

    }

};

思路2

/**

 * 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(head == nullptr || k ==1)

            return head;

        //辅助的虚拟节点

        ListNode* dummy = new ListNode(-1);

        //当前节点的上一个节点

        ListNode* lPre = dummy;

        //当前节点

        ListNode* lCur = head;

        dummy->next = head;

        int count = 0; //记录长度

        while(lCur != nullptr){

            count ++;

            if(count % k ==0){

                lPre = reverseOneGroup(lPre, lCur->next);

                lCur = lPre->next;

            }

            else{

                lCur = lCur->next;

            }

        }

        return dummy->next;

    }

    /**

     * @Description：记录节点法实现一组节点内的翻转

     * lPre：当前一组节点的上一个节点

     * lNext:当前一组节点的下一个节点

     */

    ListNode* reverseOneGroup(ListNode* lPre, ListNode* lNext){

        ListNode* lEnd = lPre->next;

        ListNode* lCur = lEnd->next;

        while(lCur != lNext){

            lEnd->next = lCur->next;

            lCur->next = lPre->next;

            lPre->next = lCur;

            lCur = lEnd->next;

        }

        return lEnd;

    }

};

Python

参考

[1] https://www.cnblogs.com/byrhuangqiang/p/4311336.html

[2] https://www.cnblogs.com/grandyang/p/4441324.html

巴特西

25. Reverse Nodes in k-Group[H]k个一组翻转链表

题目

思路