Code Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        prev = dummy

        while True:
            node = prev
            # Check if there are k nodes left to reverse
            for i in range(k):
                node = node.next
                if not node:
                    return dummy.next

            # Reverse k nodes
            curr = prev.next
            nex = curr.next
            for i in range(k - 1):
                curr.next = nex.next
                nex.next = prev.next
                prev.next = nex
                nex = curr.next

            prev = curr

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode* prev = &dummy;

        while (true) {
            ListNode* node = prev;
            // Check if there are k nodes to reverse
            for (int i = 0; i < k && node; ++i) {
                node = node->next;
            }
            if (!node) break;

            ListNode* curr = prev->next;
            ListNode* nex = curr->next;
            for (int i = 1; i < k; ++i) {
                curr->next = nex->next;
                nex->next = prev->next;
                prev->next = nex;
                nex = curr->next;
            }
            prev = curr;
        }
        return dummy.next;
    }
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;

        while (true) {
            ListNode node = prev;
            // Check if there are k nodes to reverse
            for (int i = 0; i < k && node != null; ++i) {
                node = node.next;
            }
            if (node == null) break;

            ListNode curr = prev.next;
            ListNode nex = curr.next;
            for (int i = 1; i < k; ++i) {
                curr.next = nex.next;
                nex.next = prev.next;
                prev.next = nex;
                nex = curr.next;
            }
            prev = curr;
        }
        return dummy.next;
    }
}

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function(head, k) {
    let dummy = new ListNode(0, head);
    let prev = dummy;

    while (true) {
        let node = prev;
        // Check if there are k nodes to reverse
        for (let i = 0; i < k && node; ++i) {
            node = node.next;
        }
        if (!node) break;

        let curr = prev.next;
        let nex = curr.next;
        for (let i = 1; i < k; ++i) {
            curr.next = nex.next;
            nex.next = prev.next;
            prev.next = nex;
            nex = curr.next;
        }
        prev = curr;
    }
    return dummy.next;
};

Problem Description

Given the head of a singly linked list, reverse the nodes of the list k at a time, and return the modified list. Nodes that are left with less than k elements at the end should remain in their original order.

• Each group of k nodes must be reversed as a unit.
• If the number of nodes is not a multiple of k, leave the last group as is.
• You may not alter the values inside the nodes, only the pointers/connections between nodes.
• There is only one valid output for each input.
• Do not reuse or create new nodes; rearrange the existing nodes by manipulating their next pointers.

Thought Process

At first glance, this problem seems similar to reversing a linked list, but with the added complexity of only reversing every consecutive group of k nodes. If the list is not a multiple of k, the last few nodes should remain unchanged.

The brute-force approach would be to collect k nodes, reverse them, then move to the next group. However, we need to do this in-place without extra space for the nodes themselves. This means careful pointer manipulation is required.

To optimize, we can use a dummy head node to simplify edge cases (like reversing at the head), and always check if there are enough nodes left before attempting to reverse. We need to keep track of the previous group's tail, the current node, and the next node during reversal.

Solution Approach

• Step 1: Use a Dummy Node
  • Create a dummy node that points to the head of the list. This simplifies handling the head reversal case.
• Step 2: Traverse the List in Groups
  • For each iteration, check if there are at least k nodes left. If not, stop processing.
• Step 3: Reverse k Nodes
  • Within each group, reverse the pointers for k nodes. This is done by iteratively moving each node after the head of the group to the front of the group.
  • Carefully update the next pointers to avoid losing references to the remainder of the list.
• Step 4: Move to the Next Group
  • After reversing, move the prev pointer to the end of the reversed group (which is now the start of the next group).
• Step 5: Return the Modified List
  • Return the next pointer of the dummy node, which now points to the new head.

This approach allows us to reverse nodes in-place, group by group, while maintaining the correct connections between nodes.

Example Walkthrough

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

1. First Group (1,2,3): There are at least 3 nodes, so reverse:
   • After reversal: 3 -> 2 -> 1
2. Second Group (4,5): Only 2 nodes left, which is less than k, so leave them unchanged.
3. Final List: 3 -> 2 -> 1 -> 4 -> 5

At each reversal, the code carefully updates the next pointers so that the groups are reversed in-place, and the rest of the list remains connected properly.

Time and Space Complexity

• Brute-force Approach:
  • If you used extra arrays or lists to store nodes, the time would still be O(n), but the space would be O(n).
• Optimized In-Place Approach:
  • Time Complexity: O(n), where n is the number of nodes in the list. Each node is visited a constant number of times (once for grouping, once for reversal).
  • Space Complexity: O(1), since we only use a few pointers, regardless of the input size.

Summary

This problem is a classic example of in-place linked list manipulation. By using a dummy node and carefully managing pointers, we can reverse every group of k nodes efficiently. The key insight is to always check for enough nodes before reversing and to update connections as we go, resulting in a clean and optimal O(n) time, O(1) space solution.