Well, since the head pointer may also be modified, we create a new_head that points to it to facilitate the reverse process.
For the example list 1 -> 2 -> 3 -> 4 -> 5 in the problem statement, it will become 0 -> 1 -> 2 -> 3 -> 4 -> 5 (we init new_head -> val to be 0). Then we set a pointer pre to new_head and another cur to head. Then we insert cur -> next after pre for k - 1 times if the current nodecur has at least k nodes after it (including itself). After reversing one k-group, we update pre to be cur and cur to be pre -> next to reverse the next k-group.
The code is as follows.
1 class Solution { 2 public: 3 ListNode* reverseKGroup(ListNode* head, int k) { 4 if (!hasKNodes(head, k)) return head; 5 ListNode* new_head = new ListNode(0); 6 new_head -> next = head; 7 ListNode* pre = new_head; 8 ListNode* cur = head; 9 while (hasKNodes(cur, k)) { 10 for (int i = 0; i < k - 1; i++) { 11 ListNode* temp = pre -> next; 12 pre -> next = cur -> next; 13 cur -> next = cur -> next -> next; 14 pre -> next -> next = temp; 15 } 16 pre = cur; 17 cur = pre -> next; 18 } 19 return new_head -> next; 20 } 21 private: 22 bool hasKNodes(ListNode* node, int k) { 23 int cnt = 0; 24 while (node) { 25 cnt++; 26 if (cnt >= k) return true; 27 node = node -> next; 28 } 29 return false; 30 } 31 };
