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
再链表中，每k个节点逆置，设置一个头节点，便于插入，向后寻找k个节点，将k个节点逆置，再将这k个节点接回原来的链表，继续寻找下一个k个节点逆置。。。
由于每次都扫描了两遍kgroup的节点，即扫描了两遍原链表，时间复杂度为O(n)
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution { 10 public: 11 ListNode *reverseKGroup(ListNode *head, int k) { 12 if( !head || k<2 ) return head; 13 ListNode node(-1); //设置头结点 14 node.next = head; 15 ListNode* ppre = &node; //ppre及其前面的节点都已经逆置成功 16 while( ppre->next ) { //从ppre下一个节点开始寻找 17 ListNode* tail = ppre->next; 18 ListNode* pre = ppre; 19 int cnt = 0; 20 while( tail && cnt<k ) { //寻找k个节点，tail指向第k+1个节点 21 pre = pre->next; 22 tail = tail->next; 23 ++cnt; 24 } 25 if( cnt != k ) return node.next; //如果后面的节点数不满k个，说明逆置完成 26 //如果cnt为k，说明符合逆置条件，同时tail可能为空，也可能不为空 27 pre->next = 0; //令tail成一段新的链表 28 head = ppre->next->next; //kgroup中的第一个节点时逆置后链表的第一个节点 29 ppre->next->next = tail; //连上tail 30 pre = ppre->next; //保存逆置后链表中tail的前驱指针 31 while( head ) { //使用头插法，逆置链表 32 ListNode* p = head; 33 head = head->next; 34 p->next = ppre->next; 35 ppre->next = p; 36 } 37 ppre = pre; //移向新链表 38 } 39 return node.next; 40 } 41 };
原文：http://www.cnblogs.com/bugfly/p/4003370.html