25. Reverse Nodes in k-Group

Time: O(n)

Space: O(1)

Intuition

Reverse exactly k nodes at a time, then recurse (or iterate) on the rest. The tricky part is connecting the reversed group back to the previous part and the next group. Use a dummy head to simplify the boundary.

Algorithm

1Use a dummy node before head. prevGroupTail = dummy.
2Count k nodes ahead from the current position. If fewer than k remain, stop.
3Reverse the k nodes in-place, keeping track of the new head and new tail of the reversed group.
4Connect prevGroupTail.next = newHead and newTail.next = nextGroup.
5Advance prevGroupTail to newTail. Repeat.

Example Walkthrough

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

1.Group 1: reverse [1,2] -> [2,1]. Connect: dummy->2->1.
2.Group 2: reverse [3,4] -> [4,3]. Connect: 1->4->3.
3.Only 1 node [5] left - fewer than k=2, leave as-is. Connect: 3->5.

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

Common Pitfalls

•Check there are exactly k nodes left before reversing - do not reverse a partial group.
•Save the "next group's head" before reversing, or you lose the pointer to the rest of the list.

25.cs

// Approach: Iterative k-group reversal using a dummy node to simplify head manipulation.
// For each group: first walk ahead k steps to verify enough nodes remain; if not, stop.
// Reverse the k-node segment in-place using the standard three-pointer linked-list reversal.
// Reconnect: attach the previous group's tail to the new group head, and the new group tail to the remaining list.
// Advance the 'group tail' pointer and repeat for the next group.
// Leaves any final partial group (length < k) in its original order.
// Time: O(n) Space: O(1) — purely iterative with no recursion.

public class ListNode
{
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null)
    {
        this.val = val;
        this.next = next;
    }
}

public class Solution
{
    public ListNode ReverseKGroup(ListNode head, int k)
    {
        if (head == null || k == 1) return head;
        ListNode dummy = new ListNode();
        dummy.next = head;

        ListNode prev = dummy, curr = dummy, nex = dummy;
        int cnt = 0;

        while (curr.next != null)
        {
            curr = curr.next;
            cnt++;
        }

        while (cnt >= k)
        {
            curr = prev.next;
            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;
            cnt -= k;
        }

        return dummy.next;
    }
}

Was this solution helpful?