Reverse Nodes in k-Group解题报告

Description:

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.

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

Link:

http://www.lintcode.com/en/problem/reverse-nodes-in-k-group/

解题思路：

在reverse linked list这道题的基础上，reverse这个函数的输入为（head, k）
假设k=4
原List：head->node1->node2->node3->node4->NULL
反转为：head->node4->node3->node2->node1->NULL
输出node1

否则则输出NULL

Tips:

代码注释1：
nk = nk->next;放在if语句后面，可以检测上一次反转正好把整个List反转完的情况。
代码注释2：
curr != nextPart而不是curr != nk->next是因为在循环的最后阶段nk的next会改变。

Time Complexity：

O(n)

完整代码：

ListNode *reverseKGroup(ListNode *head, int k) { ListNode *dummy = new ListNode(0); dummy->next = head; head = dummy; while(true) { head = reverse(head, k); if(head == NULL) break; } return dummy->next; } ListNode *reverse(ListNode* head, int k) { ListNode *nk = head; for(int i = 0; i < k; i++) { if(nk == NULL) return NULL; nk = nk->next; //1 } if(nk == NULL) return NULL; ListNode *endNode = head->next; ListNode *nextPart = nk->next;
ListNode *curr = head->next; ListNode *prev = NULL; ListNode *temp; while(curr != nextPart) //2 { temp = curr->next; curr->next = prev; prev = curr; curr = temp; } head->next = prev; endNode->next = nextPart; return endNode; }