143. Reorder List

Quick Identifier

Topic: linked-list
Pattern: In-place Linked List Reversal + merge
Difficulty: Medium
Companies: Facebook, Amazon, Google, Microsoft, Oracle
Frequency: High
LeetCode: 143

Quick Sights

Time Complexity: O(n) from the optimal approach.
Space Complexity: O(1) from the optimal approach.
Core Mechanism: Given a singly linked list, reorder nodes to L0 -> Ln -> L1 -> Ln-1 -> ... in place without extra O(n) space for new nodes (only pointer churn).

Concept Explanation

Given a singly linked list, reorder nodes to L0 -> Ln -> L1 -> Ln-1 -> ... in place without extra O(n) space for new nodes (only pointer churn).

The key is to state the invariant before coding: what part of the input is already settled, what state is still unresolved, and what single operation makes progress without losing correctness.

Recognition cues:

“Interleave first and last” on a list
Three steps: find middle, reverse second half, merge two lists
Linear time, O(1) extra

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Loading diagram…

Approaches

Brute force — O(n) time / O(n) space — copy to array, rewrite indices.
Better — two passes with stack for second half — O(n) space.
Optimal — O(n) time / O(1) space — slow/fast for mid, reverse tail, merge like two sorted lists but always take from alternating heads.

Optimal Solution

Go

type ListNode struct {
	Val  int
	Next *ListNode
}

func reorderList(head *ListNode) {
	if head == nil || head.Next == nil {
		return
	}
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	second := slow.Next
	slow.Next = nil
	second = reverseList(second)
	mergeInterleave(head, second)
}

func reverseList(head *ListNode) *ListNode {
	var previous *ListNode
	current := head
	for current != nil {
		next := current.Next
		current.Next = previous
		previous = current
		current = next
	}
	return previous
}

func mergeInterleave(first *ListNode, second *ListNode) {
	for second != nil {
		nextFirst := first.Next
		nextSecond := second.Next
		first.Next = second
		second.Next = nextFirst
		first = nextFirst
		second = nextSecond
	}
}

JavaScript

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

function reorderList(head) {
	if (head === null || head.next === null) {
		return;
	}
	let slow = head;
	let fast = head;
	while (fast !== null && fast.next !== null) {
		slow = slow.next;
		fast = fast.next.next;
	}
	let second = slow.next;
	slow.next = null;
	second = reverseList(second);
	mergeInterleave(head, second);
}

function reverseList(head) {
	let previous = null;
	let current = head;
	while (current !== null) {
		const next = current.next;
		current.next = previous;
		previous = current;
		current = next;
	}
	return previous;
}

function mergeInterleave(first, second) {
	while (second !== null) {
		const nextFirst = first.next;
		const nextSecond = second.next;
		first.next = second;
		second.next = nextFirst;
		first = nextFirst;
		second = nextSecond;
	}
}