LeetCode 143 · Medium · Linked List

Reorder List

Rearrange a singly linked list L0 → L1 → … → Ln in place into L0 → Ln → L1 → Ln−1 → …, alternating from the front and the back. Relink the nodes; do not change their values.

O(n)time
O(1)space
3 passesmiddle · reverse · zip

list values in order · 1–10 integers, −99 to 99

Linked list row 1 = head's chain · row 2 = the cut-off second half · slash = next is null

public void reorderList(ListNode head) { ListNode slow = head; ListNode fast = head.next; // 1. find the middle while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } ListNode second = slow.next; // 2. reverse the second half ListNode prev = null; slow.next = null; while (second != null) { ListNode tmp = second.next; second.next = prev; prev = second; second = tmp; } ListNode first = head; // 3. zip the halves second = prev; while (second != null) { ListNode tmp1 = first.next; ListNode tmp2 = second.next; first.next = second; second.next = tmp1; first = tmp1; second = tmp2; }}
slow
—
fast
—
first
—
second
—
head chain
—

Why it works

  1. Brute force copies the nodes into an array, then relinks them with two indices walking in from both ends. O(n) time but O(n) extra space for the array.
  2. The answer is two lists zipped together: the first half in order, and the second half backwards. A singly linked list cannot walk backwards, so reverse the second half once and the zip becomes a forward walk on both.
  3. Three linear passes, no extra storage: slow/fast finds the middle in n/2 hops, the reversal touches each second-half node once, and the zip touches each node once. O(n) time, O(1) space.
  4. Pitfall: cut the list at the middle (slow.next = null). Without the cut the first half still runs into the second, and the zip builds a cycle. Starting fast at head.next keeps the extra node of an odd list in the first half.
  5. Pitfall: save both next pointers first. Lines 22 and 23 overwrite first.next and second.next; tmp1 and tmp2 are the only handles left on the rest of each half.
  6. Related: Middle of the Linked List (876), Reverse Linked List (206) and Merge Two Sorted Lists (21) are the three building blocks; Palindrome Linked List (234) uses the same find-middle-and-reverse trick.