Friday, November 21, 2014

[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`

 ``` 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 && inext; 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; } }; ```

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个节点就遇到尾部。则逆向还原。