25 - Reverse Nodes in k-Group

Problem

Given the head of a linked list, reverse the nodes k at a time and return the modified list. k is a positive integer less than or equal to the length of the list. If the number of nodes is not a multiple of k, the leftover nodes at the end stay in their original order.

The values may not be modified — only the nodes themselves may be changed.

Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]

Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]

Constraints:

• The number of nodes is n, with 1 <= k <= n <= 5000
• 0 <= Node.val <= 1000

Follow-up: do it in O(1) extra memory space.

Approach

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(k == 1) return head;
        ListNode* m = head;
        int n = 0;
        while(m) {
            n++;
            m = m->next;
        }
        int x = n / k;
        ListNode dummy(0, head);
        ListNode *b = &dummy;
        ListNode* curr = b->next;
        ListNode* left = curr;
        while(x--) {
            ListNode* prev = nullptr;
            int p = k;
            while(p--) {
                ListNode* next = curr->next;
                curr->next = prev;
                prev = curr;
                curr = next;
            }
            b->next = prev;
            left->next = curr;
            b = left;
            left = curr;
        }
        return dummy.next;
    }
};

• time: O(n) - one pass to count, one pass reversing each node exactly once
• space: O(1) - five pointers and a stack-allocated dummy, no recursion