Reorder List

The problem

You are given head, the first node of a linked list. Put the nodes in this order: the first node, the last node, the second node, the second-to-last node, and so on inward, until every node is used once. Return the first node of the reordered list. A node holds a value, val, and a link, next, to the node after it, and the last node's next is null. An empty list is given as null and returned as null. You may relink the given nodes or build new ones.

What to write

type ListNode = {val:number;next:ListNode|null};

function solve(head: ListNode | null): ListNode | null

Input
head = {"val":1,"next":{"val":2,"next":{"val":3,"next":{"val":4,"next":null}}}}

Output
{"val":1,"next":{"val":4,"next":{"val":2,"next":{"val":3,"next":null}}}}

Input
head = {"val":1,"next":{"val":2,"next":{"val":3,"next":{"val":4,"next":{"val":5,"next":null}}}}}

Output
{"val":1,"next":{"val":5,"next":{"val":2,"next":{"val":4,"next":{"val":3,"next":null}}}}}

Constraints

Lists are represented by nested {val, next} objects and contain at most 50000 nodes.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The list can hold 50,000 nodes, and a node only links forward. Walking from the front to find the last node, then again for the one before it, and so on, would take hundreds of millions of steps on a list that long.

2. Hint 2: Ask a smaller question

   Write the answer for 1 → 2 → 3 → 4 → 5 by hand: 1, 5, 2, 4, 3. Now read only every second value, starting from the 5. Where do those nodes come from, and in what order do they appear?

3. Hint 3: Name the pattern

   The answer alternates between the first half in its own order and the second half backward. So find the middle, reverse the second half, and weave the two halves together, all by changing links. That is linked list pointer rewiring: the same nodes in a new order. Read the lesson on linked list pointer rewiring.

4. Hint 4: State the invariant

   After the cut and the reversal there are two separate lists: the first half in its original order and the second half backward. During the weave, the nodes not yet used in each half are still linked in that order, so the next node to take is always at the front of a half.

5. Hint 5: Sketch the pseudocode

   Return a list of fewer than two nodes unchanged. Move a slow marker by one node and a fast marker by two until the fast one cannot move. Cut the list after the slow marker and reverse the second half. While that half has nodes: put its front node after the current first-half node, then move on in both halves.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Split at the midpoint, reverse the second half, and alternate nodes from both halves.

The slow way

For each position, walk to the end of the list, unlink the last node, and put it after the current node. Then move two nodes forward and repeat. It is correct, but every round walks the rest of the list again: about n × n / 4 steps, which is 625 million for 50,000 nodes.

The insight

The new order alternates between two sequences: the first half read forward and the second half read backward. A linked list cannot be read backward, but a reversed list can be read forward. So reverse the second half, and the task becomes taking nodes from two lists in turn.

Step by step

1. An empty list or a single node is already in its final order. With fewer than two nodes there is nothing to move. Returning here also keeps the code below from reading the link of a node that does not exist.
2. Find the middle: one marker moves one node, another moves two. A marker is a variable that points at one node. The fast marker moves twice as quickly, so when it cannot jump two more nodes, the slow marker stands on the last node of the first half.
3. Cut the list in two after the middle node. The first half has to end at the middle node. If that node kept its old link into the second half, the finished list would run in a circle and never end.
4. Reverse the second half. The new order takes nodes from the back: the last, then the one before it. A list can only be read forward, so the second half is turned around, and its first node is then the old last node.
5. Weave the two halves together, one node from each in turn. Each round puts the front node of the reversed half right after the current node of the first half. The next node of both halves is saved first, because the round overwrites both links.
6. The first node never moved, so it is still the head. The reordered list starts with the original first node. Every other node was linked in somewhere behind it, so the head you were given is the answer.

The same numbered steps are the comments in each solution.

function solve(head) {
  // 1. An empty list or a single node is already in its final order
  if (!head?.next) return head;
  // 2. Find the middle: one marker moves one node, another moves two
  let slow = head,
    fast = head;
  while (fast?.next?.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  // 3. Cut the list in two after the middle node
  let cur = slow.next;
  slow.next = null;
  // 4. Reverse the second half
  let prev = null;
  while (cur) {
    const next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }
  // 5. Weave the two halves together, one node from each in turn
  let first = head;
  while (prev) {
    const a = first.next,
      b = prev.next;
    first.next = prev;
    prev.next = a;
    first = a;
    prev = b;
  }
  // 6. The first node never moved, so it is still the head
  return head;
}

type ListNode = { val: number; next: ListNode | null };
function solve(head: ListNode | null): ListNode | null {
  // 1. An empty list or a single node is already in its final order
  if (!head?.next) return head;
  // 2. Find the middle: one marker moves one node, another moves two
  let slow: ListNode = head,
    fast: ListNode | null = head;
  while (fast?.next?.next) {
    slow = slow.next!;
    fast = fast.next.next;
  }
  // 3. Cut the list in two after the middle node
  let cur = slow.next;
  slow.next = null;
  // 4. Reverse the second half
  let prev: ListNode | null = null;
  while (cur) {
    const next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }
  // 5. Weave the two halves together, one node from each in turn
  let first: ListNode | null = head;
  while (prev) {
    const a: ListNode | null = first!.next,
      b: ListNode | null = prev.next;
    first!.next = prev;
    prev.next = a;
    first = a;
    prev = b;
  }
  // 6. The first node never moved, so it is still the head
  return head;
}

def solve(head):
    # 1. An empty list or a single node is already in its final order
    if not head or not head.next:
        return head
    # 2. Find the middle: one marker moves one node, another moves two
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    # 3. Cut the list in two after the middle node
    cur = slow.next
    slow.next = None
    # 4. Reverse the second half
    prev = None
    while cur:
        after = cur.next
        cur.next = prev
        prev = cur
        cur = after
    # 5. Weave the two halves together, one node from each in turn
    first, second = head, prev
    while second:
        after_first, after_second = first.next, second.next
        first.next = second
        second.next = after_first
        first, second = after_first, after_second
    # 6. The first node never moved, so it is still the head
    return head

Example 2, traced

Input
head = {"val":1,"next":{"val":2,"next":{"val":3,"next":{"val":4,"next":{"val":5,"next":null}}}}}

Output
{"val":1,"next":{"val":5,"next":{"val":2,"next":{"val":4,"next":{"val":3,"next":null}}}}}

Why it works

After the cut and the reversal there are two lists: the first half in its original order and the second half backward. The first has as many nodes as the second, or one more. Taking one node from each in turn, first half first, gives first, last, second, second to last, until both are used up.

Time and space

Time O(n), extra space O(1). Finding the middle, reversing the second half and weaving are three walks, each over at most n nodes, so the time is O(n). All of it is done by changing the links of the given nodes, with a fixed number of references and no new nodes: O(1) extra space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Cut the list after the middle node before you weave. If that node keeps its old link, the end of the result points back into the list, and the answer goes round in a cycle.
• In the weave, save both next nodes before you change a link. If you follow the second half's link after changing it, nodes are lost: 1 → 2 → 3 → 4 gives 1 → 4 → 2.
• Handle the empty list before anything else. head can be null, and reading the link of null is an error.

Pattern

Linked list pointer rewiring. Builds on Reverse Linked List and Merge Two Sorted Lists.

Keep going