Reverse Nodes In K-Group

NeetCode: Reverse Nodes In K-Group · LeetCode: 25. Reverse Nodes In K-Group · Difficulty: Hard

Reverse the nodes of a list k at a time and return the modified list. If the number of remaining nodes is less than k, leave them as they are. Only node links may change, not values.

Example

Text

Input:  1 -> 2 -> 3 -> 4 -> 5, k = 2    Output: 2 -> 1 -> 4 -> 3 -> 5
Input:  1 -> 2 -> 3 -> 4 -> 5, k = 3    Output: 3 -> 2 -> 1 -> 4 -> 5

A ListNode holds an int val and a next reference that is null at the end of the list. The fromArray helper builds a list from its values and toList reads one back, so the examples can print results.

Brute force: reverse chunks of an ArrayList

Collections.reverse reverses a list in place, and subList(from, to) is a view of part of an ArrayList, so reversing the view reverses that range of the original.

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        List<Integer> values = new ArrayList<>();
        for (ListNode cur = head; cur != null; cur = cur.next) {
            values.add(cur.val);
        }
        for (int i = 0; i + k <= values.size(); i += k) {
            Collections.reverse(values.subList(i, i + k)); // only full groups
        }
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (int val : values) {
            tail.next = new ListNode(val);
            tail = tail.next;
        }
        return dummy.next;
    }
}

public class Main {
    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static List<Integer> toList(ListNode head) {
        List<Integer> out = new ArrayList<>();
        for (ListNode cur = head; cur != null; cur = cur.next) {
            out.add(cur.val);
        }
        return out;
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(toList(s.reverseKGroup(fromArray(1, 2, 3, 4, 5), 2)));
        System.out.println(toList(s.reverseKGroup(fromArray(1, 2, 3, 4, 5), 3)));
    }
}

Output

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

Time: O(n). Space: O(n).

Optimal: count the groups, reverse each one in place

Count the nodes once. len / k full groups exist and the remainder stays untouched. Keep a dummy node in front and a tail reference to the last node of the finished part. For each group:

Remember groupStart = tail.next. It becomes the last node of the group after reversal.
Reverse exactly k nodes with the three-reference loop (prev, cur, next) from the reverse-list lesson. What is left in cur is the rest of the list.
Set tail.next to the reversed group and groupStart.next to cur. Then move tail to groupStart.

Example 1 -> 2 -> 3 -> 4 -> 5, k = 2: two full groups. Group 1, 2 becomes 2 -> 1, tail moves to node 1, and 3 -> 4 -> 5 is next. Group 3, 4 becomes 4 -> 3, giving 2 -> 1 -> 4 -> 3 -> 5.

Java

import java.util.ArrayList;
import java.util.List;

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        int len = 0;
        for (ListNode p = head; p != null; p = p.next) {
            len++;
        }

        ListNode dummy = new ListNode(0, head);
        ListNode tail = dummy;
        for (int g = 0; g < len / k; g++) {
            ListNode groupStart = tail.next; // becomes the last node of the group
            ListNode rev = null;
            ListNode cur = groupStart;
            for (int i = 0; i < k; i++) {
                ListNode next = cur.next;
                cur.next = rev;
                rev = cur;
                cur = next;
            }
            tail.next = rev;        // reversed group
            groupStart.next = cur;  // rest of the list
            tail = groupStart;
        }
        return dummy.next;
    }
}

public class Main {
    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static List<Integer> toList(ListNode head) {
        List<Integer> out = new ArrayList<>();
        for (ListNode cur = head; cur != null; cur = cur.next) {
            out.add(cur.val);
        }
        return out;
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(toList(s.reverseKGroup(fromArray(1, 2, 3, 4, 5), 2)));
        System.out.println(toList(s.reverseKGroup(fromArray(1, 2, 3, 4, 5), 3)));
        System.out.println(toList(s.reverseKGroup(fromArray(1, 2, 3), 1)));
        System.out.println(toList(s.reverseKGroup(fromArray(1, 2), 3)));
    }
}

Output

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

Time: O(n): one pass to count, then each node is reversed once. Space: O(1) extra. A recursive version that solves the rest of the list first is shorter but uses O(n / k) stack.

How to explain it in an interview

Say first: "Copy the values to a list, reverse each full chunk of k, rebuild the list: O(n) time and space, but it does not rewire nodes."
Key insight: each full group is independent: reverse k nodes, then link the group to the previous group's tail and to the rest of the list.
Code it in steps: (1) count the length; (2) dummy node and tail; (3) for each of len / k groups, remember the first node and reverse k nodes; (4) attach the reversed group to tail, attach the rest after the old first node, move tail to it.
Complexity to state: O(n) time, O(1) extra space.
Likely follow-ups / pitfalls: a short final group stays in original order because only len / k groups are reversed; k = 1 changes nothing. A recursive solution is acceptable but uses O(n / k) stack.