Link to Question

HARD

Reverse Nodes in k-Group

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

k is a positive integer and is less than or equal to the length of the linked 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 list's nodes, only nodes themselves may be changed.

Example

Input:

head = [1,2,3,4,5], k = 2

Output:

[2,1,4,3,5]

Explanation:
The list is reversed in groups of 2.

---

Constraints

• The number of nodes in the list is n.
• 1 ≤ k ≤ n ≤ 5000
• 0 ≤ Node.val ≤ 1000

---

Solution: Iterative

• Time Complexity: O(n)
• Space Complexity: O(1)

C++

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* start = dummy;
        while(start->next) {
            ListNode* cur = start;
            for(int i = 0; i < k && cur; i++) cur = cur->next;
            if (cur == nullptr) break;
            ListNode* new_start = start->next;
            ListNode* n = cur->next;
            ListNode* pre = nullptr;
            ListNode* it = start->next;
            while(pre != cur) {
                ListNode* t = it->next;
                it->next = pre;
                pre = it;
                it = t;
            }
            start->next->next = n;
            start->next = pre;
            start = new_start;

        }
        return dummy->next;
    }
};