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; }
