题解 | #链表中的节点每k个一组翻转#
链表中的节点每k个一组翻转
http://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e
思路
正序，即从前往后按步长k遍历并翻转，然后每个子链表首尾拼接； 即：
- 如何链表长度＜2，则直接返回；
- 定义全局变量节点：curr,用来记录当前要执行反转的开始开始位置节点；然后逐个k长子链翻转，最后用递归从后向前首尾链接；
- 定义计数值i = 0， 然后从curr节点开始，逐个节点前后翻转，翻转的子链表长度为k；
- 当 i == k 或者 curr == nullptr 时，退出子翻转，保存子链表翻转后的头结点：prev; 此时curr变量已更新为下一个要翻转子链的开始节点；
- 让该子链表的尾节点的next节点指向下一个翻转好的子节点的头结点；因此最后一步用到递归，实现从后向前逐段子链首尾链接；
- 若最后一段子链长度＜k, 则将其再次翻转为正序并返回；
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
class Solution {
public:
/**
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
ListNode* curr; //定义全局变量节点：curr,用来记录当前要执行反转的开始开始位置节点；
bool start = true;
ListNode* reverseKGroup(ListNode* head, int k) {
// write code here
if(!head || !head->next || k < 2) {
return head;
}
return reverse_List(head, k);
}
//从curr节点开始，逐个节点前后翻转，翻转的子链表长度为k
ListNode* reverse_List(ListNode* head, int k) {
if(!head) {
return nullptr;
}
curr = head;
ListNode* prev = nullptr;
int i = 0;
while (curr && i < k) {
ListNode* rear = curr->next;
curr->next = prev;
prev = curr;
curr = rear;
++i;
}
// 若最后一段子链长度＜k, 则将其再次翻转为正序并返回；
if(i > 0 && i < k) {
return reverse_SubList(prev, i);
}
// 让该子链表的尾节点的next节点指向下一个翻转好的子节点的头结点；因此最后一步用到递归
head->next = reverse_List(curr, k);
return prev;
}
ListNode* reverse_SubList(ListNode *head, int k) {
ListNode* cur = head;
ListNode* prev = nullptr;
while(cur && k--) {
ListNode* next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
};
