LeetCode - Reverse Nodes in k-Group

 1 // 1RE, 1AC, good.
 2 /**
 3  * Definition for singly-linked list.
 4  * struct ListNode {
 5  *     int val;
 6  *     ListNode *next;
 7  *     ListNode(int x) : val(x), next(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     ListNode *reverseKGroup(ListNode *head, int k) {
13         if (head == nullptr || k < 2) {
14             // no change at all
15             return head;
16         }
17         ListNode *bh, *h, *t, *at;
18         
19         bh = nullptr;
20         h = head;
21         int i;
22         while (true) {
23             if (h == nullptr) {
24                 break;
25             }
26             t = h;
27             for (i = 1; i < k; ++i) {
28                 t = t->next;
29                 if (t == nullptr) {
30                     break;
31                 }
32             }
33             if (i == k) {
34                 at = t->next;
35                 t->next = nullptr;
36                 reverseList(h, t);
37                 if (bh != nullptr) {
38                     // put the segment in place again
39                     bh->next = h;
40                     t->next = at;
41                 } else {
42                     // the first group will change the head of the list
43                     head = h;
44                     t->next = at;
45                 }
46                 // find the next group
47                 bh = t;
48                 h = at;
49             } else {
50                 break;
51             }
52         }
53         
54         
55         return head;
56     }
57 private:
58     void reverseList(ListNode *&h, ListNode *&t) {
59         if (h == nullptr || t == nullptr) {
60             // impossible
61             return;
62         }
63         if (h == t) {
64             // only one node
65             return;
66         }
67         
68         ListNode *new_h, *new_t;
69         ListNode *ptr, *tmp;
70         
71         new_h = nullptr;
72         ptr = h;
73         while (ptr != nullptr) {
74             if (new_h == nullptr) {
75                 new_h = new_t = ptr;
76                 ptr = ptr->next;
77                 new_h->next = nullptr;
78             } else {
79                 tmp = ptr->next;
80                 ptr->next = new_h;
81                 new_h = ptr;
82                 ptr = tmp;
83             }
84         }
85         
86         h = new_h;
87         t = new_t;
88     }
89 };