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這道題的基礎(chǔ)上，reverse這個函數(shù)的輸入為（head, k）
假設(shè)k=4
原List：head->node1->node2->node3->node4->NULL
反轉(zhuǎn)為：head->node4->node3->node2->node1->NULL
輸出node1

否則則輸出NULL

Tips:

代碼注釋1：
nk = nk->next;放在if語句后面，可以檢測上一次反轉(zhuǎn)正好把整個List反轉(zhuǎn)完的情況。
代碼注釋2：
curr != nextPart而不是curr != nk->next是因為在循環(huán)的最后階段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; }