← DSA Atlas
Dedicated problem page · #143

Reorder List

MediumLinked Lists and Pointer ManipulationFind middle, reverse second half, merge alternatelyFast/slow split plus in-place reversal and interleave
Solve on LeetCode ↗
143
MediumLinked Lists and Pointer ManipulationFast/slow split plus in-place reversal and interleaveFind middle, reverse second half, merge alternately

Reorder List

Given the head of a singly linked list L0 -> L1 -> ... -> Ln-1 -> Ln, reorder it in place to L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ... You may not change node values, only rearrange the nodes themselves.

Open official problem prompt ↗
In plain English

Rearrange the nodes into the front-back weave in place, touching each node a constant number of times.

Picture it like this

Deal a deck by splitting it in half, flipping the bottom half over, and then dealing one card from the top half, one from the flipped half, alternating.

Example
Input
head = [1, 2, 3, 4]
Output
[1, 4, 2, 3]
Why
The list is woven from both ends inward: first node, then last, then second, then second-to-last.
Constraints
The number of nodes is in the range [1, 5 * 10^4]1 <= Node.val <= 1000
Pattern lesson

See the pattern, then code

Find middle, reverse second half, merge alternately
Recognition clue

A reorder that interleaves the front of the list with its reversed back half signals the compound find-middle + reverse + merge routine.

↗
Linked Lists and Pointer Manipulation

Reversal, cycle detection, merging, reordering, or O(1)-space sequence edits.. Splitting at the middle gives a front half and a back half; reversing the back half lets you zip the two halves together one node at a time to achieve the front-back-front-back weave.

New words, made simpleKnow these before the algorithm
Middle node
The end of the first half; found by advancing slow one step per two steps of fast.
Interleave
Combining two lists by alternating one node from each.
In-place reversal
Flipping next pointers of the second half without extra storage.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Store nodes in an array and re-link by index

Simple but uses linear extra memory.

Push all nodes into a list, then rewire using two indices from both ends.

Time O(n)Space O(n)
Best choiceSplit, reverse, merge

Constant space and the expected in-place technique.

Locate the middle, reverse the back half, then zip the halves together.

Time O(n)Space O(1)
The rule we keep true

Invariant

After the split, the first half has ceil(n/2) nodes and the reversed second half has floor(n/2) nodes, so the merge never reads past the end of the shorter half.

Why this is correct

Reasoning

Reversing the back half turns Ln, Ln-1, ... into a forward list; alternately linking first-half and reversed-back-half nodes yields exactly L0, Ln, L1, Ln-1, ..., and setting slow.next=None prevents a cycle.

The algorithm in three movesSay these aloud before coding
1Find the middle with slow/fast pointers and cut the list into two halves

mid split: 1->2 | 3->4

2Reverse the second half in place

reverse back: 4->3

3Merge the two halves by alternating nodes from each

merge: 1->4->2->3

4Because the operation is in place, the function returns None

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
21
32
43
1 · Read[1,2,3,4]
2 · AskWhere to cut?
3 · Update stateslow=2
4 · Resultfront=1->2, back=3->4
Key takeaway

The list is halved, the back half is flipped, then the two halves are interleaved from their heads.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-4Trivial cases

    Lists of length 0 or 1 are already reordered.

  2. 2
    Lines 5-10Split at the middle

    slow lands on the last node of the first half; cutting slow.next isolates the two halves.

  3. 3
    Lines 11-16Reverse the second half

    Standard three-pointer flip so the back half runs from the old tail forward.

  4. 4
    Lines 17-24Zip the halves

    Save both successors, relink first->prev->first's old next, and advance both pointers.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Single node returns unchanged
  • Two nodes stay as L0 -> L1
  • Odd length keeps the extra middle node in the first half
!

Common beginner mistakes

  • Forgetting slow.next = None, which leaves a link creating a cycle during the merge
  • Using fast/fast.next as the loop guard instead of fast.next/fast.next.next, splitting at the wrong node
  • Losing successor references during the merge by not caching f_nxt and p_nxt
Check your understanding

Why does the merge loop terminate correctly when n is odd?

More in Linked Lists and Pointer Manipulation

#206Reverse Linked ListIterative pointer reversal#141Linked List CycleFast and slow pointers (Floyd's cycle detection)#138Copy List with Random PointerClone with old-to-new node mapping#146LRU CacheHash map plus recency-ordered structure#2Add Two NumbersDigit-by-digit addition with carry#19Remove Nth Node From EndFixed-gap two pointers