Reverse Nodes In K Group

Difficulty: Hard Source: NeetCode

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• Reversing a Linked List — in-place reversal of a sublist (see problems 1 and 9)
• Dummy Head Trick — sentinel node to uniformly handle the first group
• Group Boundary Detection — checking if k nodes remain before committing to a reversal

1. Recursive Approach

Intuition

Think about the problem recursively: reverse the first k nodes, then recursively reverse the rest, and connect them. Before reversing, check if there are at least k nodes remaining — if not, leave them as is.

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

Check: 2 nodes remaining? Yes.
Reverse first 2: [2,1] and save pointer to node 3.
Recurse on [3,4,5]:
  Check: 2 nodes remaining? Yes.
  Reverse first 2: [4,3] and save pointer to node 5.
  Recurse on [5]:
    Check: 2 nodes remaining? No. Return head (5) unchanged.
  Connect: 3.next = 5
  Return 4 (head of reversed [4,3,5])
Connect: 1.next = result of recursion = [4,3,5]
Return 2 (head of reversed [2,1,4,3,5])

Algorithm

1. Check if at least k nodes exist starting from head. If not, return head.
2. Reverse the first k nodes, keeping track of the k-th node and the node after it.
3. The original head becomes the tail of the reversed group. Connect it to reverseKGroup(k+1th node, k).
4. Return the k-th node (new head of this group).

Solution

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

def build_list(values):
    if not values:
        return None
    head = ListNode(values[0])
    cur = head
    for v in values[1:]:
        cur.next = ListNode(v)
        cur = cur.next
    return head

def print_list(head):
    result = []
    while head:
        result.append(str(head.val))
        head = head.next
    print(" -> ".join(result) if result else "None")

def reverseKGroup_recursive(head, k):
    # Check if there are at least k nodes
    count = 0
    cur = head
    while cur and count < k:
        cur = cur.next
        count += 1
    if count < k:
        return head  # fewer than k nodes left, don't reverse

    # Reverse k nodes starting from head
    prev = None
    curr = head
    for _ in range(k):
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    # After loop:
    # prev = k-th node (new head of this reversed group)
    # curr = (k+1)-th node (start of remaining list)
    # head = original head (now the tail of the reversed group)

    # Recursively reverse the rest and connect
    head.next = reverseKGroup_recursive(curr, k)

    return prev  # new head of this group

# Test cases
head = build_list([1, 2, 3, 4, 5])
print("Output: ", end=""); print_list(reverseKGroup_recursive(head, 2))  # 2->1->4->3->5

head2 = build_list([1, 2, 3, 4, 5])
print("Output: ", end=""); print_list(reverseKGroup_recursive(head2, 3))  # 3->2->1->4->5

head3 = build_list([1, 2, 3, 4, 5])
print("Output: ", end=""); print_list(reverseKGroup_recursive(head3, 1))  # 1->2->3->4->5

head4 = build_list([1, 2, 3, 4, 5])
print("Output: ", end=""); print_list(reverseKGroup_recursive(head4, 5))  # 5->4->3->2->1

head5 = build_list([1])
print("Output: ", end=""); print_list(reverseKGroup_recursive(head5, 1))  # 1

Complexity

• Time: O(n) — each node is visited a constant number of times
• Space: O(n/k) — recursion stack depth (one frame per group)

2. Iterative with Dummy Head (Optimal)

Intuition

The recursive approach has O(n/k) stack depth. We can eliminate the recursion by iterating group by group, carefully tracking four pointers at each step:

• group_prev — the node just before the current group (starts as dummy)
• group_next — the node just after the current group
• The current group itself (k nodes starting from group_prev.next)

For each group:

1. Find the k-th node from group_prev. If it doesn’t exist, stop.
2. Save group_next = kth_node.next, then reverse the group.
3. Re-attach: group_prev.next = kth_node (new head), original_head.next = group_next.
4. Advance group_prev = original_head (which is now the tail of the reversed group).

dummy -> 1 -> 2 -> 3 -> 4 -> 5, k=2

group_prev = dummy
Find kth node (k=2): node 2
group_next = node 3
Reverse [1,2]: prev=2->1->None, curr=3
Re-attach: dummy.next = 2, 1.next = 3
Advance: group_prev = node 1

State: dummy -> 2 -> 1 -> 3 -> 4 -> 5
group_prev = node 1
Find kth node: node 4
group_next = node 5
Reverse [3,4]: prev=4->3->None, curr=5
Re-attach: 1.next = 4, 3.next = 5
Advance: group_prev = node 3

State: dummy -> 2 -> 1 -> 4 -> 3 -> 5
group_prev = node 3
Find kth node: only node 5 exists, count < k, stop.

Result: 2 -> 1 -> 4 -> 3 -> 5

Algorithm

1. Create dummy node, set group_prev = dummy.
2. Loop: a. Find the k-th node from group_prev. If not found, break. b. Save the start of this group: group_start = group_prev.next. c. Save the node after the group: group_next = kth.next. d. Disconnect the group: kth.next = None. e. Reverse the group (returns new head = original kth node). f. Re-attach: group_prev.next = reversed_head, group_start.next = group_next. g. Advance group_prev = group_start.
3. Return dummy.next.

Solution

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

def build_list(values):
    if not values:
        return None
    head = ListNode(values[0])
    cur = head
    for v in values[1:]:
        cur.next = ListNode(v)
        cur = cur.next
    return head

def print_list(head):
    result = []
    while head:
        result.append(str(head.val))
        head = head.next
    print(" -> ".join(result) if result else "None")

def get_kth(node, k):
    """Return the k-th node from 'node' (1-indexed), or None if not enough nodes."""
    while node and k > 0:
        node = node.next
        k -= 1
    return node  # None if fewer than k nodes remain

def reverseKGroup(head, k):
    dummy = ListNode(0, head)
    group_prev = dummy

    while True:
        # Find the k-th node in the current group
        kth = get_kth(group_prev, k)
        if not kth:
            break  # fewer than k nodes left, stop

        group_start = group_prev.next  # first node of current group
        group_next = kth.next          # first node of next group

        # Reverse the group [group_start ... kth]
        # Disconnect from rest first
        kth.next = None
        prev = None
        cur = group_start
        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
        # prev = kth (new head), group_start = old head (new tail)

        # Re-attach
        group_prev.next = prev           # connect to new head of reversed group
        group_start.next = group_next    # connect tail of reversed group to remainder

        # Advance group_prev to the tail of the just-reversed group
        group_prev = group_start

    return dummy.next

# Test cases
head = build_list([1, 2, 3, 4, 5])
print("Output: ", end=""); print_list(reverseKGroup(head, 2))  # 2->1->4->3->5

head2 = build_list([1, 2, 3, 4, 5])
print("Output: ", end=""); print_list(reverseKGroup(head2, 3))  # 3->2->1->4->5

head3 = build_list([1, 2, 3, 4, 5])
print("Output: ", end=""); print_list(reverseKGroup(head3, 1))  # 1->2->3->4->5

head4 = build_list([1, 2, 3, 4, 5])
print("Output: ", end=""); print_list(reverseKGroup(head4, 5))  # 5->4->3->2->1

head5 = build_list([1, 2])
print("Output: ", end=""); print_list(reverseKGroup(head5, 2))  # 2->1

# Remainder left untouched
head6 = build_list([1, 2, 3, 4])
print("Output: ", end=""); print_list(reverseKGroup(head6, 3))  # 3->2->1->4

Complexity

• Time: O(n) — each node is reversed exactly once
• Space: O(1) — no recursion, only a constant number of pointers

Common Pitfalls

Not checking for k remaining nodes before reversing. If you reverse whenever you can, you’ll flip the last partial group too. Always call get_kth first and bail if there aren’t enough nodes.

Losing the connection to the next group. Before reversing, always save group_next = kth.next. After reversing, the tail of the reversed group (group_start) must point to group_next, not None.

Not advancing group_prev correctly. After reversing a group, group_prev should move to group_start (the old head, now the tail). This is where the next group begins. If you advance to the new head instead, you’ll process the same nodes again.

Off-by-one in get_kth. The function get_kth(node, k) finds the k-th node from node by advancing k times from node (not from node.next). Make sure you advance exactly k times and return the result — return None if the loop exits because node became None.