Reorder List

Split, reverse, weave

Combines three techniques: find middle, reverse second half, merge.

Published Apr 15, 2026

Problem

Given the head of a singly linked list, reorder it in-place so that the node order becomes:

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

You must preserve the node values and only change pointers.

Input

head = [1,2,3,4]

Output

[1,4,2,3]

Input

head = [1,2,3,4,5]

Output

[1,5,2,4,3]

Intuition

This is not a new linked-list trick. It is three old ones composed together:

find the midpoint
reverse the second half
merge the two halves by alternating nodes

The target order starts at both ends of the list and walks inward. That is exactly why splitting and reversing help: once the back half is reversed, the two halves line up in the order you want to weave them.

The hard part is not the algorithm. It is keeping ownership and next pointers consistent while you perform the three structural edits.

Approach

Split, Reverse, Weave

TimeO(n)

SpaceO(1)

Recommended

Find the midpoint, cut the list in half, reverse the second half, then alternate nodes from the front and back halves until the back half is exhausted.

The middle node stays on the front side when the list length is odd.

impl Solution {
    pub fn reorder_list(head: &mut Option<Box<ListNode>>) {
        fn reverse(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
            let mut prev = None;

            while let Some(mut curr) = head {
                head = curr.next.take();
                curr.next = prev;
                prev = Some(curr);
            }

            prev
        }

        let mut len = 0;
        let mut cursor = head.as_ref();
        while let Some(node) = cursor {
            len += 1;
            cursor = node.next.as_ref();
        }

        if len < 2 {
            return;
        }

        let mut mid= head.as_mut().unwrap();
        for _ in 0..((len - 1) / 2) {
            mid= mid.next.as_mut().unwrap();
        }

        let mut second= reverse(mid.next.take());
        let mut first_cursor= head.as_mut();

        while let Some(node1)= first_cursor {
            if second.is_none() {
                break;
            }

            let mut node2= second.take().unwrap();
            second= node2.next.take();

            let next1= node1.next.take();
            node1.next= Some(node2);

            let next_cursor= {
                let inserted= node1.next.as_mut().unwrap();
                inserted.next= next1;
                inserted.next.as_mut()
            };

            first_cursor= next_cursor;
        }
    }
}

Rust · runnable

function reorderList(head: ListNode | null): void {
  if (head === null || head.next === null) return;

  let slow: ListNode | null = head;
  let fast: ListNode | null = head.next;
  while (fast !== null && fast.next !== null) {
    slow = slow!.next;
    fast = fast.next.next;
  }

  let second = slow!.next;
  slow!.next = null;

  let prev: ListNode | null = null;
  while (second !== null) {
    const next = second.next;
    second.next = prev;
    prev = second;
    second = next;
  }
  second = prev;

  let first: ListNode | null = head;
  while (second !== null) {
    const next1 = first!.next;
    const next2 = second.next;

    first!.next = second;
    second.next = next1;

    first = next1;
    second = next2;
  }
}

TypeScript · runnable

Trace

On head = [1,2,3,4,5]:

phase	front half	back half	list shape
split	[1,2,3]	[4,5]	1 -> 2 -> 3
reverse	[1,2,3]	[5,4]	5 -> 4
weave	[1,2,3]	[5,4]	1 -> 5 -> 2 -> 4 -> 3

The list is never copied. The pointers are simply rearranged in place.

Edge cases

Length 0 or 1 — already ordered; return immediately.
Length 2 — reversing the second half does nothing interesting; the weave step terminates after one splice.
Odd length — the middle node stays at the end of the merged list.

Takeaway

Reorder List is a composition problem. Once you can split, reverse, and weave a linked list without losing pointers, you have the core skill set for the rest of this track.

Easy#206

Reverse Linked List

Three pointers: prev, curr, next. Draw it out. Do both iterative and recursive.

Easy#21

Merge Two Sorted Lists

Merge step of merge sort. In Rust, practice with Option<Box<ListNode>>.

Hard#23

Merge k Sorted Lists