☕ DSA Java Articles

Topics › Linked List › Medium Problems of LL

Reorder List

Easy TUF ID 2407 Blind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given the head of a singly linked list L0 -> L1 -> ... -> Ln-1 -> Ln. Reorder it in place into

L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ...

that is, alternate between taking a node from the front and a node from the back. You may only change next pointers; the values inside the nodes must not be modified. The function returns nothing; the head stays the same node.

Constraints: 1 ≤ n ≤ 5 × 10^4 nodes in the LeetCode version, values fit in an int. The Java solutions also accept an empty list.

static class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

Example 1

head   = 1 -> 2 -> 3 -> 4
result = 1 -> 4 -> 2 -> 3        // front, back, front, back

Example 2

head   = 1 -> 2 -> 3 -> 4 -> 5
result = 1 -> 5 -> 2 -> 4 -> 3   // the middle node 3 ends up last

The Java tests check node identity, not just values: position k of the result must be the very same object that was at original position 0, n-1, 1, n-2, .... That catches any solution that cheats by copying values around.

Approach 1: Brute force, move the tail forward repeatedly

Intuition. Do literally what the output describes. Standing on the first node, the node that must come next is the current tail. Detach the tail and splice it in right after the current node. Then step to the next untouched front node and repeat: the new tail is the next node to splice in. Each splice fixes two positions of the output for good.

The loop stops when fewer than three nodes remain from cur onwards. With one node there is nothing to do, and with two nodes cur -> x, the node x is already the tail and already directly after cur.

Algorithm.

  1. Set cur = head.
  2. While cur, cur.next and cur.next.next all exist:
    • Walk prev from cur to the node just before the tail, and let tail = prev.next.
    • Detach it: prev.next = null.
    • Splice it after cur: tail.next = cur.next, cur.next = tail.
    • Move cur = tail.next, the next front node.
static void bruteForce(ListNode head) {
    ListNode cur = head;
    while (cur != null && cur.next != null && cur.next.next != null) {
        ListNode prev = cur;                     // walk to the node before the tail
        while (prev.next.next != null) prev = prev.next;
        ListNode tail = prev.next;
        prev.next = null;                        // detach the tail
        tail.next = cur.next;                    // and splice it in right after cur
        cur.next = tail;
        cur = tail.next;                         // continue from the next untouched front node
    }
}

Complexity. Time O(n^2): there are about n / 2 splices, and each needs a walk to the tail, which is O(n) in a singly linked list. Space O(1).

The cost is all in finding the tail again and again. A singly linked list can only be traversed forwards, so “give me the back” is expensive. The next two approaches fix that in two different ways.

Approach 2: Better, an array of node references

Intuition. If you could index the nodes, you would just use two indices: i from the front and j from the back, and link nodes[i] -> nodes[j] -> nodes[i + 1] -> nodes[j - 1] -> ... until they meet. So copy the node references into an ArrayList first. You are still relinking the original nodes, not copying values.

The detail that is easy to forget is the last link. The node where i and j meet becomes the new tail, but it still points to its old successor from the original order. Unless you set its next to null, the list contains a cycle.

Algorithm.

  1. Store every node in nodes; set i = 0, j = n - 1.
  2. While i < j:
    • Link nodes[i].next = nodes[j] and increment i. If now i == j, stop.
    • Link nodes[j].next = nodes[i] and decrement j.
  3. Set nodes[i].next = null.
static void better(ListNode head) {
    if (head == null) return;
    List<ListNode> nodes = new ArrayList<>();
    for (ListNode t = head; t != null; t = t.next) nodes.add(t);
    int i = 0, j = nodes.size() - 1;
    while (i < j) {
        nodes.get(i).next = nodes.get(j);        // front -> back
        i++;
        if (i == j) break;
        nodes.get(j).next = nodes.get(i);        // back -> next front
        j--;
    }
    nodes.get(i).next = null;                    // the node where i and j meet is the new tail
}

Complexity. Time O(n): one pass to fill the array and one pass to relink. Space O(n) for the array of references. The memory is the only thing left to improve.

Approach 3: Optimal, split, reverse, weave

Intuition. Look at the result again: 1 -> 5 -> 2 -> 4 -> 3. The odd positions are 1, 2, 3, the first half in its original order. The even positions are 5, 4, the second half in reversed order. So the output is simply the first half interleaved with the reversed second half, and each of those three steps is a standard constant-space linked list technique:

  1. Find the middle with slow and fast pointers. Use the condition fast.next != null && fast.next.next != null, so that slow stops on the last node of the first half and the first half is never shorter than the second. For odd n the extra node stays in the first half, which is right because the middle node must end up last.
  2. Reverse the second half in place, after cutting it off with slow.next = null. The cut matters: without it the first half would still run into the second half and the weave would create a cycle.
  3. Weave the halves: take one node from the first half, then one from the reversed second half, and repeat until the second half runs out. Because the first half is at least as long, first is never null while second still has nodes.

Algorithm.

  1. If the list has fewer than two nodes, return.
  2. Move slow and fast from the head until fast cannot take two more steps; slow is the end of the first half.
  3. second = reverse(slow.next), then slow.next = null.
  4. With first = head, while second is not empty: save n1 = first.next and n2 = second.next, link first -> second -> n1, then move first = n1 and second = n2.
static void optimal(ListNode head) {
    if (head == null || head.next == null) return;
    ListNode slow = head, fast = head;           // slow ends on the last node of the first half
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode second = reverse(slow.next);        // second half, back to front
    slow.next = null;                            // cut the first half off
    ListNode first = head;
    while (second != null) {                     // second half is never longer than the first
        ListNode n1 = first.next, n2 = second.next;
        first.next = second;
        second.next = n1;
        first = n1;
        second = n2;
    }
}

static ListNode reverse(ListNode head) {
    ListNode prev = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

Dry run on 1 -> 2 -> 3 -> 4 -> 5:

phase state
find middle slow stops on 3 (fast on 5)
cut first half 1 -> 2 -> 3, second half 4 -> 5
reverse second half 5 -> 4
weave 1 1 -> 5 -> 2, first = 2, second = 4
weave 2 1 -> 5 -> 2 -> 4 -> 3, first = 3, second = empty

Node 3 already has next == null from the cut, so the list is properly terminated. On 1 -> 2 -> 3 -> 4, slow stops on 2, the halves are 1 -> 2 and 4 -> 3, and the weave gives 1 -> 4 -> 2 -> 3.

Complexity. Time O(n): finding the middle, reversing and weaving are each a single linear pass. Space O(1): a handful of pointers and no recursion.

Edge cases and pitfalls