Leetcode 25. Reverse Nodes in k-Group

Clarification

Okay, so first I’ll restate the problem to make sure I understand it correctly. We are given the head of a linked list and an integer k. We need to reverse every group of k nodes. If the remaining nodes are fewer than k, we leave them as they are.

So for example: 1 -> 2 -> 3 -> 4 -> 5, k = 2 should become: 2 -> 1 -> 4 -> 3 -> 5.

Should I return the new head of the linked list?
Can the list be empty?
Can k > list.length?
Are we reversing the nodes themselves, not just swapping values?

Brute-force Approach

A simple idea is to put all nodes into an array, reverse each group of k, and then reconnect them. That works, but it uses O(n) extra space.

Optimized Approach

A better solution is to reverse the linked list in place group by group.

First, I’ll use a dummy node before the head because reversing the first group may change the head. Then for each group, I need to know two important positions: start marks the node before the current group and end marks the last node of the current group. Then I'll need a helper function that reverses the group and return the tail of the reversed group, which becomes the new start for the next group. And then in the main function we can keep moving forward and reversing each group until the end points to null.

I believe the helper function can be written recursively. The base case is that if the group only has one node left, it is already reversed. For the recursive case we need to shrink down the problem size. First I'll keep the start.next as s. Before we do the recursive call, let assume the list looking like start s t - - end. After the recursive call, the list should be start s end - - t. Then we can move s to the end of list and clean up other connections, by the three lines in the code. Finally we return s because it is the tail of the reversed list over the original list.

The time is O(n) because each node is processed once per group. The space is O(k) because reverseList uses recursion up to k nodes deep.

Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     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) {
        ListNode dummy = new ListNode(0, head);
        ListNode start = dummy, end = dummy;

        while (end != null) {
            for (int i = 0; i < k && end != null; i++)
                end = end.next;
            if (end == null)   break;

            start = reverseList(start, end);
            end = start;
        }

        return dummy.next;

    }

    // reverse a list between (start, end]
    // return the tail of the reversed list
    private ListNode reverseList(ListNode start, ListNode end) {
        if (start.next == end)
            return end;

        ListNode s = start.next;
        ListNode t = reverseList(s, end);
        start.next = s.next;
        s.next = t.next;
        t.next = s;

        return s;
    }

    // start s t - - end
    // reverse (s, end]
    // start s end - - t
    // start end - - t s
    // start end - - - s
}

Follow-up

We can write reverseList in the iterative way to achieve the same in-place reversal effect while reducing the space to O(1).