25. Reverse Nodes in k-Group

 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(k==1||head==NULL)
13             return head;
14         ListNode *helpleft = new ListNode(0);
15         helpleft->next = head;
16         ListNode *helpright = new ListNode(0);
17         while(head->next!=NULL)
18             head = head->next;
19         head->next = helpright;
20         ListNode *pre=helpleft;
21         head = helpleft->next;
22         ListNode *beh;
23         ListNode *tail;
24         ListNode *ss;
25         ListNode *p = head;
26         int count = 1;
27         while(p!=helpright){
28             if(count==k){
29                 beh = p->next;
30                 tail = p;
31                 reverse(pre, beh, head, tail);
32                 count = 1;
33                 pre = head;
34                 ss = pre;
35                 head = beh;
36                 p = beh;
37             }
38             else{
39                 ss = p;
40                 p = p->next;
41                 count++;
42             }
43         }
44         ss->next = NULL;
45         delete(helpright);
46         head = helpleft->next;
47         helpleft->next = NULL;
48         delete(helpleft);
49         return head;
50     }
51
52     void reverse(ListNode *pre, ListNode *beh, ListNode *head, ListNode *tail){
53         ListNode *p = head;
54         ListNode *k = head;
55         while(k!=beh){
56             k = k->next;
57             p->next = pre->next;
58             pre->next = p;
59             p = k;
60         }
61         head->next = beh;
62         return;
63     }
64 };

就是前后指针卡住要逆置的链表段，原地逆置，再接回去

这里要注意的是，逆置过后，head和tail位置互换了，所以下一组逆置序列中，pre指向的是head