33. Reorder List

MediumLinked List Two Pointers Recursion

You are given the head of a singly linked list whose nodes, in order, are L0, L1, L2, …, Ln.

Rearrange it in place so that the nodes alternate from the two ends: L0, Ln, L1, Ln-1, L2, Ln-2, …

Only change the next links; do not modify the values stored in the nodes. The function returns nothing; the list starting at head is checked afterwards.

Example 1

Input: head = [5,6,7,8]
Output: [5,8,6,7]

Example 2

Input: head = [10,20,30,40,50]
Output: [10,50,20,40,30]

Explanation: With an odd number of nodes, the middle node ends up last.

Constraints

The number of nodes is in the range [1, 5 * 10^4]
-1000 <= Node.val <= 1000

💡 Hint 1

The new order interleaves the first half of the list with the second half read backwards.

💡 Hint 2

Find the middle with slow and fast pointers, then reverse the second half in place.

💡 Hint 3

Finally merge the two halves by alternating one node from each, starting with the first half.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

The target order interleaves the first half with the reversed second half, and each piece is a standard linked-list move:

Find the middle with a slow pointer (one step) and a fast pointer (two steps). When fast can't advance, slow is the last node of the first half.
Cut and reverse the list after slow, so the second half now runs Ln, Ln-1, ….
Weave the halves: take one node from the first half, then one from the reversed second half, repeating until the second half is used up. The first half is equal or one longer, so its last node already ends the list.

Everything is done by relinking, with a constant number of pointers. Copying the nodes into an array and rebuilding the links also works, but costs O(n) extra space.

Time O(n)Space O(1)

function reorderList(head) {
  if (!head || !head.next) return;
  let slow = head;
  let fast = head;
  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  let prev = null;
  let curr = slow.next;
  slow.next = null;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  let first = head;
  let second = prev;
  while (second) {
    const firstNext = first.next;
    const secondNext = second.next;
    first.next = second;
    second.next = firstNext;
    first = firstNext;
    second = secondNext;
  }
}

class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode prev = null, curr = slow.next;
        slow.next = null;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        ListNode first = head, second = prev;
        while (second != null) {
            ListNode firstNext = first.next, secondNext = second.next;
            first.next = second;
            second.next = firstNext;
            first = firstNext;
            second = secondNext;
        }
    }
}

/**
 * Definition for singly-linked list (provided):
 * function ListNode(val, next) { this.val = val ?? 0; this.next = next ?? null; }
 *
 * @param {ListNode} head
 * @return {void} Reorder the list in place.
 */
function reorderList(head) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit