[LeetCode] Reverse Nodes in k-Group

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

思路:

Swap Nodes in Pairs那题的升级版，算linked list指针操作题中难度最高最容易写错的之一。思路很简单，就是每次反转k个节点，如果还没反转到i<k个节点就遇到尾部了，则将这i个节点再反转回来。但要短时间内写正确却难度不小。这类题目一定要画图来验证解法是否正确。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

class Solution { public: ListNode *reverseKGroup(ListNode *head, int k) { if(k<2) return head; ListNode *dummy = new ListNode(0); dummy->next = head; ListNode *p = dummy; while(p->next && p->next->next) { ListNode *prev = p->next, *cur = prev->next; int i=0; while(cur && i<k-1) { ListNode *temp = cur->next; cur->next = prev; prev = cur; cur = temp; i++; } if(i==k-1) { // k nodes reversed ListNode *temp = p->next; p->next->next = cur; p->next = prev; p = temp; } else { // less than k nodes reversed before reach end cur = prev->next; prev->next = NULL; while(cur != p->next) { ListNode *temp = cur->next; cur->next = prev; prev = cur; cur = temp; } break; } } return dummy->next; } };

总结：

几乎用到linked list题所有的技巧。

1. p指针总是指向每次要反转的k个节点的前一个节点。因为反转后仍然要接回这个节点之后。

2. ln8：如果p指针后没有节点或只剩一个节点了，那么整个反转结束。

3. ln11-17：尝试反转k个节点，如果遇到尾部，则提前结束。i记录了反转多少次。注意，要反转k个节点的话，实际反转指针只需要k-1次。

4. ln19-24：如果成功反转k个节点，则i=k-1。此时将反转的k个节点两头接回，并将p移动到反转后k个节点的最后一个节点处，以备继续反转之后的k个节点。

5. ln25-35：如果没能反转k个节点就遇到尾部。则逆向还原。