Reverse Nodes in k-Group

Hard Problem 61 of 151 Java and Python

Problem

Given the head of a linked list, reverse its nodes k at a time and return the modified list. If the number of nodes left at the end is less than k, leave them in their original order.

Change the links, not the values.

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]
Why: Only 4 and 5 are left, fewer than 3, so they stay.

Constraints

1 ≤ k ≤ n ≤ 5000
Follow-up: O(1) extra memory.

Explanation

Handle one group at a time. Keep groupPrev, the node just before the current group. First check that k nodes exist; if not, stop.

Reverse the k nodes the usual way, then reconnect: groupPrev must point to the new first node (the old last), and the old first node becomes the groupPrev for the next group.

Approach 1 · Naive

Reverse values through an array

Time O(n)
Space O(n)

Copy the values to an array, reverse every full block of k, and write the values back. Simple, but it changes values and uses O(n) memory, which the problem disallows.

Collect values.
Reverse each full block [i, i + k).
Write the values back into the nodes.

Java

import java.util.*;

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        List<Integer> values = new ArrayList<>();
        for (ListNode n = head; n != null; n = n.next) {
            values.add(n.val);
        }
        for (int i = 0; i + k <= values.size(); i += k) {
            Collections.reverse(values.subList(i, i + k));
        }
        int i = 0;
        for (ListNode n = head; n != null; n = n.next) {
            n.val = values.get(i++);
        }
        return head;
    }
}

Python

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        values, node = [], head
        while node:
            values.append(node.val)
            node = node.next
        for i in range(0, len(values) - k + 1, k):
            values[i:i + k] = values[i:i + k][::-1]
        node = head
        for v in values:
            node.val = v
            node = node.next
        return head

Approach 2 · Optimal

Reverse each group in place

Time O(n)
Space O(1)

With a dummy head, repeatedly find the k-th node after groupPrev, reverse the group between them, and stitch it back.

Set groupPrev = dummy.
Find kth, the k-th node after groupPrev; if it does not exist, stop. Let groupNext = kth.next.
Reverse the nodes from groupPrev.next up to kth, pointing the first one at groupNext.
Set groupPrev.next = kth and move groupPrev to the old first node.

Java

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0, head);
        ListNode groupPrev = dummy;
        while (true) {
            ListNode kth = groupPrev;
            for (int i = 0; i < k && kth != null; i++) {
                kth = kth.next;
            }
            if (kth == null) {
                break;
            }
            ListNode groupNext = kth.next;
            ListNode prev = groupNext;
            ListNode curr = groupPrev.next;
            while (curr != groupNext) {
                ListNode next = curr.next;
                curr.next = prev;
                prev = curr;
                curr = next;
            }
            ListNode first = groupPrev.next;
            groupPrev.next = kth;
            groupPrev = first;
        }
        return dummy.next;
    }
}

Python

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        group_prev = dummy
        while True:
            kth = group_prev
            for _ in range(k):
                kth = kth.next
                if not kth:
                    return dummy.next
            group_next = kth.next
            prev, curr = group_next, group_prev.next
            while curr is not group_next:
                curr.next, prev, curr = prev, curr, curr.next
            first = group_prev.next
            group_prev.next = kth
            group_prev = first

Complexity compared

Approach	Time	Space
Naive Reverse values through an array	O(n)	O(n)
Optimal Reverse each group in place	O(n)	O(1)

Key takeaways

Starting prev at groupNext (instead of null) connects the reversed group to the rest of the list for free.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem