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

题目

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

参考