Problem Statement

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.

Additional information

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

Example 1:

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

Output: [2, 1, 4, 3, 5]

Example 2:

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

Output: [3, 2, 1, 4, 5]

Brute Force (Array Replacement)

Intuition

The easiest way to reverse chunks of a linked list without getting confused by pointers is to extract all the node values into a standard Python array. Once the values are in an array, we can easily reverse them in chunks of size k using array slicing. Finally, we can rebuild a brand new linked list from the modified array.

Algorithm

1. Traverse the linked list and append all values to an array vals.
2. Iterate through vals in steps of k (for i in range(0, len(vals), k)).
3. For each chunk, if the remaining elements are at least k in number (i + k <= len(vals)), reverse that slice in the array: vals[i:i+k] = reversed(vals[i:i+k]).
4. Create a dummy node to act as the head of a new linked list.
5. Iterate through the modified vals array, creating a new ListNode for each value and attaching it to the chain.
6. Return dummy.next.

def reverse_k_group(head: Optional[ListNode], k: int) -> Optional[ListNode]:
    vals = []
    curr = head
    
    # Extract values
    while curr:
        vals.append(curr.val)
        curr = curr.next
        
    # Reverse in chunks of k
    for i in range(0, len(vals), k):
        if i + k <= len(vals):
            vals[i:i+k] = reversed(vals[i:i+k])
            
    # Build new list
    dummy = ListNode(0)
    curr = dummy
    for v in vals:
        curr.next = ListNode(v)
        curr = curr.next
        
    return dummy.next

Time & Space Complexity

• Time complexity: O(n)

• Reason: We iterate through the list to extract values, reverse chunks in the array (which takes linear time overall), and iterate again to build the new list.

• Space complexity: O(n)

• Reason: We store all n values in an array and create n completely new nodes.

In-Place Reversal (Optimal)

Intuition

To achieve O(1) space, we must modify the pointers of the existing linked list directly.
We can process the list group by group. For each group, we first look ahead k steps to ensure there are enough nodes to reverse. If there are, we reverse just those k nodes.

We need to keep track of the group_prev node (the node just before the current group) so we can reconnect the newly reversed group back into the main list.

Algorithm

1. Create a dummy node pointing to head. Initialize group_prev = dummy.
2. Start an infinite loop (while True):

• Find the kth node of the current group. Start from group_prev and move forward k times.
• If we hit None before reaching k, we don't have enough nodes left. Break out of the loop.
• Save group_next = kth.next. This is the start of the next group.
• Reverse the group: Use standard linked list reversal. Set prev = group_next and curr = group_prev.next. Loop k times to reverse the pointers.
• Reconnect: After reversal, the original first node of the group (which is now the last node of the reversed group) needs to become the new group_prev for the next iteration. Update group_prev.next = kth (the new head of the group), and then step group_prev forward.

3. Return dummy.next.

def reverse_k_group(head: Optional[ListNode], k: int) -> Optional[ListNode]:
    dummy = ListNode(0, head)
    group_prev = dummy
    
    while True:
        # Find the kth node of this group
        kth = group_prev
        for _ in range(k):
            kth = kth.next
            if not kth:
                break
                
        # If we didn't find k nodes, we are done
        if not kth:
            break
            
        group_next = kth.next
        
        # Reverse the current group
        prev, curr = group_next, group_prev.next
        for _ in range(k):
            tmp = curr.next
            curr.next = prev
            prev = curr
            curr = tmp
            
        # Reconnect the reversed group to the rest of the list
        tmp = group_prev.next
        group_prev.next = kth
        group_prev = tmp
        
    return dummy.next

Time & Space Complexity

• Time complexity: O(n)

• Reason: We traverse the list to find the kth node, and then traverse it again to reverse the pointers. Each node is touched at most twice.

• Space complexity: O(1)

• Reason: We only use a few pointer variables (dummy, group_prev, kth, prev, curr) to manipulate the list in-place.