143. Reorder List (Medium)

Problem

Given a singly linked list L: L₀ → L₁ → … → Lₙ₋₁ → Lₙ, reorder it in place so that it becomes L₀ → Lₙ → L₁ → Lₙ₋₁ → L₂ → Lₙ₋₂ → ….

Example

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

LeetCode 143 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, copy to array, re-link by index

Walk the list into an array; use two pointers from both ends to reassemble.

Python

def reorder_list(head) -> None:
    if not head:
        return
    nodes = []
    cur = head
    while cur:
        nodes.append(cur)          # L1: O(1) per node, n total
        cur = cur.next
    i, j = 0, len(nodes) - 1
    while i < j:                   # L2: n/2 iterations
        nodes[i].next = nodes[j]   # L3: O(1) splice
        i += 1
        if i == j:
            break
        nodes[j].next = nodes[i]   # L4: O(1) splice
        j -= 1
    nodes[i].next = None

TypeScript

class ListNode {
    val: number; next: ListNode | null;
    constructor(val = 0, next: ListNode | null = null) { this.val = val; this.next = next; }
}

function reorderList(head: ListNode | null): void {
    if (!head) return;
    const nodes: ListNode[] = [];
    let cur: ListNode | null = head;
    while (cur) {
        nodes.push(cur);           // L1: O(1) per node, n total
        cur = cur.next;
    }
    let i = 0, j = nodes.length - 1;
    while (i < j) {               // L2: n/2 iterations
        nodes[i].next = nodes[j]; // L3: O(1) splice
        i++;
        if (i === j) break;
        nodes[j].next = nodes[i]; // L4: O(1) splice
        j--;
    }
    nodes[i].next = null;
}

Swift

final class Solution {
func reorderList(_ head: ListNode?) {
        var nodes: [ListNode] = []
        var current = head
        while let node = current {
            nodes.append(node)
            current = node.next
        }
        var order: [ListNode] = []
        var left = 0
        var right = nodes.count - 1
        while left <= right && left < nodes.count {
            order.append(nodes[left])
            if left != right { order.append(nodes[right]) }
            left += 1
            right -= 1
        }
        for index in order.indices {
            order[index].next = index + 1 < order.count ? order[index + 1] : nil
        }
    }
}

Where the time goes, line by line

Variables: n = number of nodes in the list.

Line	Per-call cost	Times executed	Contribution
L1 (collect)	$O(1)$	n	$O(n)$
L2-L4 (re-link)	$O(1)$	n/2	$O(n)$ ← dominates

Both phases are $O(n)$. The array costs $O(n)$ extra space but simplifies the two-ended access to $O(1)$ per step.

Complexity

• Time: $O(n)$, driven by L1 and L2-L4 equally.
• Space: $O(n)$ for the array.

Approach 2: Use a deque (slightly cleaner)

Push nodes into a deque; pop alternately from the left and right.

Python

from collections import deque

def reorder_list(head) -> None:
    if not head:
        return
    dq = deque()
    cur = head
    while cur:
        dq.append(cur)             # L1: O(1) per node
        cur = cur.next
    take_left = True
    tail = None
    while dq:                      # L2: n iterations
        node = dq.popleft() if take_left else dq.pop()  # L3: O(1) deque pop
        if tail:
            tail.next = node       # L4: O(1) link
        tail = node
        take_left = not take_left
    tail.next = None

TypeScript

function reorderList(head: ListNode | null): void {
    if (!head) return;
    const nodes: ListNode[] = [];
    let cur: ListNode | null = head;
    while (cur) { nodes.push(cur); cur = cur.next; }  // L1: O(1) per node
    let left = 0, right = nodes.length - 1;
    let takeLeft = true;
    let tail: ListNode | null = null;
    while (left <= right) {        // L2: n iterations
        const node = takeLeft ? nodes[left++] : nodes[right--];  // L3: O(1) pick
        if (tail) tail.next = node;  // L4: O(1) link
        tail = node;
        takeLeft = !takeLeft;
    }
    tail!.next = null;
}

Swift

final class Solution {
func reorderList(_ head: ListNode?) {
        var deque: [ListNode] = []
        var current = head
        while let node = current {
            deque.append(node)
            current = node.next
        }
        guard !deque.isEmpty else { return }
        var left = 0
        var right = deque.count - 1
        var tail = deque[left]
        left += 1
        var takeRight = true
        while left <= right {
            let next = takeRight ? deque[right] : deque[left]
            if takeRight { right -= 1 } else { left += 1 }
            tail.next = next
            tail = next
            takeRight.toggle()
        }
        tail.next = nil
    }
}

Where the time goes, line by line

Variables: n = number of nodes in the list.

Line	Per-call cost	Times executed	Contribution
L1 (build deque)	$O(1)$	n	$O(n)$
L2-L4 (drain + link)	$O(1)$	n	$O(n)$ ← dominates

Same asymptotics as Approach 1 but deque’s $O(1)$ popleft avoids the index bookkeeping.

Complexity

• Time: $O(n)$, driven by L1 and L2-L4 equally.
• Space: $O(n)$ for the deque.

Approach 3: Find middle + reverse second half + merge (optimal)

Three sub-routines, each $O(n)$ and $O(1)$ space:

1. Find middle with slow/fast pointers.
2. Reverse the second half in place.
3. Weave the two halves.

Python

def reorder_list(head) -> None:
    if not head or not head.next:
        return

    # 1. Find middle (slow ends at middle)
    slow = fast = head
    while fast.next and fast.next.next:   # L1: slow/fast to find mid
        slow = slow.next                   # L2: O(1) advance slow
        fast = fast.next.next             # L3: O(1) advance fast

    # 2. Reverse second half
    prev, curr = None, slow.next
    slow.next = None     # cut the list in two
    while curr:
        nxt = curr.next
        curr.next = prev                   # L4: O(1) pointer reversal
        prev = curr
        curr = nxt
    second = prev

    # 3. Weave
    first = head
    while second:                          # L5: n/2 iterations
        t1 = first.next
        t2 = second.next
        first.next = second               # L6: O(1) splice
        second.next = t1                  # L7: O(1) splice
        first = t1
        second = t2

TypeScript

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

    // 1. Find middle
    let slow: ListNode = head, fast: ListNode | null = head;
    while (fast.next && fast.next.next) {
        slow = slow.next!;                 // L2: O(1) advance slow
        fast = fast.next.next;            // L3: O(1) advance fast
    }

    // 2. Reverse second half
    let prev: ListNode | null = null;
    let curr: ListNode | null = slow.next;
    slow.next = null;
    while (curr) {
        const nxt = curr.next;
        curr.next = prev;                  // L4: O(1) pointer reversal
        prev = curr;
        curr = nxt;
    }
    let second = prev;

    // 3. Weave
    let first: ListNode | null = head;
    while (second) {                       // L5: n/2 iterations
        const t1 = first!.next;
        const t2 = second.next;
        first!.next = second;             // L6: O(1) splice
        second.next = t1;                 // L7: O(1) splice
        first = t1;
        second = t2;
    }
}

Swift

final class Solution {
func reorderList(_ head: ListNode?) {
        guard let head, head.next != nil else { return }
        var slow: ListNode? = head
        var fast: ListNode? = head
        while fast?.next != nil && fast?.next?.next != nil {
            slow = slow?.next
            fast = fast?.next?.next
        }
        var second = slow?.next
        slow?.next = nil
        var previous: ListNode?
        while let node = second {
            let next = node.next
            node.next = previous
            previous = node
            second = next
        }
        var first: ListNode? = head
        second = previous
        while let right = second {
            let firstNext = first?.next
            let secondNext = right.next
            first?.next = right
            right.next = firstNext
            first = firstNext
            second = secondNext
        }
    }
}

Where the time goes, line by line

Variables: n = number of nodes in the list.

Line	Per-call cost	Times executed	Contribution
L1-L3 (find middle)	$O(1)$	n/2	$O(n)$
L4 (reverse)	$O(1)$	n/2	$O(n)$
L5-L7 (weave)	$O(1)$	n/2	$O(n)$ ← all three phases equal

Three independent $O(n)$ passes, each touching n/2 nodes. No extra allocation. The cut at slow.next = None is essential: it prevents the weave loop from running into the reversed half before it’s consumed.

Complexity

• Time: $O(n)$. Three linear passes (L1-L3, L4, L5-L7).
• Space: $O(1)$.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_143.py and run.
# Uses the find-middle + reverse + weave approach (Approach 3).

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

def from_list(vals):
    dummy = ListNode()
    cur = dummy
    for v in vals:
        cur.next = ListNode(v)
        cur = cur.next
    return dummy.next

def reorder_list(head) -> None:
    if not head or not head.next:
        return
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    prev, curr = None, slow.next
    slow.next = None
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    second = prev
    first = head
    while second:
        t1 = first.next
        t2 = second.next
        first.next = second
        second.next = t1
        first = t1
        second = t2

def _run_tests():
    # Even length: [1,2,3,4] -> [1,4,2,3]
    h = from_list([1,2,3,4])
    reorder_list(h)
    assert to_list(h) == [1,4,2,3]

    # Odd length: [1,2,3,4,5] -> [1,5,2,4,3]
    h = from_list([1,2,3,4,5])
    reorder_list(h)
    assert to_list(h) == [1,5,2,4,3]

    # Single node: no change
    h = from_list([1])
    reorder_list(h)
    assert to_list(h) == [1]

    # Two nodes: [1,2] -> [1,2]
    h = from_list([1,2])
    reorder_list(h)
    assert to_list(h) == [1,2]

    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

class ListNode {
    val: number; next: ListNode | null;
    constructor(val = 0, next: ListNode | null = null) { this.val = val; this.next = next; }
}

function toList(head: ListNode | null): number[] {
    const out: number[] = [];
    while (head) { out.push(head.val); head = head.next; }
    return out;
}

function fromList(vals: number[]): ListNode | null {
    const dummy = new ListNode();
    let cur = dummy;
    for (const v of vals) { cur.next = new ListNode(v); cur = cur.next; }
    return dummy.next;
}

function reorderList(head: ListNode | null): void {
    if (!head || !head.next) return;
    let slow: ListNode = head, fast: ListNode | null = head;
    while (fast.next && fast.next.next) { slow = slow.next!; fast = fast.next.next; }
    let prev: ListNode | null = null, curr: ListNode | null = slow.next;
    slow.next = null;
    while (curr) { const nxt = curr.next; curr.next = prev; prev = curr; curr = nxt; }
    let second = prev, first: ListNode | null = head;
    while (second) {
        const t1 = first!.next, t2 = second.next;
        first!.next = second; second.next = t1;
        first = t1; second = t2;
    }
}

const h1 = fromList([1,2,3,4]); reorderList(h1);
console.assert(JSON.stringify(toList(h1)) === JSON.stringify([1,4,2,3]));
const h2 = fromList([1,2,3,4,5]); reorderList(h2);
console.assert(JSON.stringify(toList(h2)) === JSON.stringify([1,5,2,4,3]));
const h3 = fromList([1]); reorderList(h3);
console.assert(JSON.stringify(toList(h3)) === JSON.stringify([1]));
const h4 = fromList([1,2]); reorderList(h4);
console.assert(JSON.stringify(toList(h4)) === JSON.stringify([1,2]));
console.log("all tests pass");

Summary

Approach	Time	Space
Array of nodes	$O(n)$	$O(n)$
Deque	$O(n)$	$O(n)$
Find middle + reverse + weave	$O(n)$	$O(1)$

The optimal approach composes three fundamental linked-list moves, it’s the canonical test that you know the primitives.

Related data structures

• Linked Lists, three-primitive composition

Related concepts

• Linked List Pointer Rewiring, the link editing pattern for changing node order without losing the chain.
• Fast and Slow Pointers, the pointer speed trick for finding middles, cycles, and distance from the end.