View on NeetCode
View on LeetCode

Problem

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 is.

You may not alter the values in the list’s nodes, only nodes themselves may be changed.

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]

Constraints:

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

Follow-up: Can you solve the problem in O(1) extra memory space?

Solution

Approach: Iterative Reversal with Pointer Tracking

The key insight is to process the list in groups of k nodes. For each group, we reverse it and connect it properly to the previous and next groups.

Algorithm:

1. Check if there are k nodes remaining
2. Reverse the k nodes
3. Connect the reversed group to previous and next parts
4. Move to the next group
5. Repeat until fewer than k nodes remain

Implementation

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # Check if we have k nodes to reverse
        def hasKNodes(node, k):
            count = 0
            while node and count < k:
                node = node.next
                count += 1
            return count == k

        # Reverse k nodes starting from head
        def reverseK(head, k):
            prev = None
            curr = head
            for _ in range(k):
                next_node = curr.next
                curr.next = prev
                prev = curr
                curr = next_node
            return prev, curr  # New head, next group head

        dummy = ListNode(0, head)
        group_prev = dummy

        while hasKNodes(group_prev.next, k):
            # Save group start
            group_start = group_prev.next

            # Reverse k nodes
            new_head, next_group = reverseK(group_start, k)

            # Connect reversed group
            group_prev.next = new_head
            group_start.next = next_group

            # Move to next group
            group_prev = group_start

        return dummy.next

Alternative (Recursive):

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # Check if we have k nodes
        curr = head
        count = 0
        while curr and count < k:
            curr = curr.next
            count += 1

        # If we have k nodes, reverse them
        if count == k:
            # Reverse k nodes
            prev = None
            curr = head
            for _ in range(k):
                next_node = curr.next
                curr.next = prev
                prev = curr
                curr = next_node

            # head is now the last node of reversed group
            # Recursively process remaining nodes
            head.next = self.reverseKGroup(curr, k)
            return prev  # New head of reversed group

        # Less than k nodes, return as is
        return head

Complexity Analysis

• Time Complexity: O(n), where n is the number of nodes. We visit each node twice: once to check if k nodes exist, once to reverse.
• Space Complexity: O(1) for iterative, O(n/k) for recursive due to call stack.

Key Insights

1. Group Validation: Before reversing each group, we must verify that k nodes exist. If not, we leave them unchanged.

2. Pointer Tracking: We need to track:
   • group_prev: last node of the previous group
   • group_start: first node of current group (becomes last after reversal)
   • new_head: new first node after reversal
   • next_group: first node of next group
3. Connection Pattern: After reversing a group:
   • group_prev.next = new_head (connect previous group to reversed group’s head)
   • group_start.next = next_group (connect reversed group’s tail to next group)

4. Dummy Node: A dummy node simplifies handling the first group, which becomes the new head of the entire list.

5. Recursive Elegance: The recursive approach is cleaner - reverse k nodes, then recursively process the rest. The base case handles when fewer than k nodes remain.