Skip to content
16-Week DSA Roadmap
LeetCode #143MediumProblem 8 of 8

Reorder List

Rearrange a list into first, last, second, second-to-last, ... in place, by finding the middle, reversing the second half, and zipping the halves together.

  • Combining patterns
  • Fast and slow pointers
  • Reversing a linked list

Before this, know: Reverse Linked List, Fast and slow pointers (Linked List Cycle)

The problem in plain English

You get head, the first node of a linked list L0 → L1 → … → Ln. Rearrange it to

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

that is: first, last, second, second-to-last, and so on, like shuffling a deck by alternately taking from the top and the bottom. Change the links, not the values, and do it in place: the function returns nothing.

before
12345
after
15243
[1, 2, 3, 4, 5] becomes 1 → 5 → 2 → 4 → 3. Front nodes (blue) alternate with back nodes (amber); the middle node 3 ends up last.

The rules that matter:

  • Up to 50,000 nodes. Lists with 0, 1 or 2 nodes stay exactly as they are.
  • You may not just swap values; you must rewire the nodes.
  • The answer is checked by walking the list from head after your function runs.

Before you code: think it through

Look at the target again: 1, 5, 2, 4, 3. The odd positions are 1, 2, 3 (the first half, in order). The even positions are 5, 4 (the second half, backwards). So the job breaks into three smaller jobs, each one a pattern you already know:

  1. Find the middle, with slow and fast pointers (like Linked List Cycle).
  2. Reverse the second half, with prev / curr / next (like Reverse Linked List).
  3. Merge the two halves, taking one node from each in turn (like Merge Two Sorted Lists, but alternating instead of comparing).

Pause and think

For [1, 2, 3, 4, 5, 6], what are the two halves after phase 2, and what is the final order?

Approach 1: Copy the nodes into an array

A linked list can’t jump to “the last node”, but an array can. So copy every node (not just its value) into an array, then use two indexes: i from the front and j from the back. Link nodes[i] → nodes[j] → nodes[i + 1] → … until they meet. The node where they meet is the new tail.

Brute force: an array of nodes, zipped from both ends

head = [1, 2, 3, 4]

nodes (array of node references)
  1. 10
1234
  • nodes[i] (front)
  • nodes[j] (back)
  • Link just changed
  • Done

Copy node 1 into the array. Arrays let us jump to any position, which a linked list can't do.

Step 1 / 9

Which line is running?

function reorderList(head) {  const nodes = [];  let node = head;  while (node !== null) { // copy every node into an arrayRunning now:     nodes.push(node);    node = node.next;  }  let i = 0;  let j = nodes.length - 1;  while (i < j) {    nodes[i].next = nodes[j]; // front -> back    i++;    if (i === j) break;    nodes[j].next = nodes[i]; // back -> next front    j--;  }  if (nodes.length > 0) nodes[i].next = null; // the middle node is the new tail}

Array of nodes + two indexes

function reorderList(head) {  const nodes = [];  let node = head;  while (node !== null) { // copy every node into an array    nodes.push(node);    node = node.next;  }  let i = 0;  let j = nodes.length - 1;  while (i < j) {    nodes[i].next = nodes[j]; // front -> back    i++;    if (i === j) break;    nodes[j].next = nodes[i]; // back -> next front    j--;  }  if (nodes.length > 0) nodes[i].next = null; // the middle node is the new tail}
def reorder_list(head):    nodes = []    node = head    while node is not None:  # copy every node into a list        nodes.append(node)        node = node.next    i, j = 0, len(nodes) - 1    while i < j:        nodes[i].next = nodes[j]  # front -> back        i += 1        if i == j:            break        nodes[j].next = nodes[i]  # back -> next front        j -= 1    if nodes:        nodes[i].next = None  # the middle node is the new tail

Why isn’t it good enough?

The time is fine: O(n). But the array holds a reference to every node: O(n) extra memory, 50,000 slots for a 50,000-node list. The interviewer will ask for O(1) extra space, and that’s where the three-phase solution comes in.

The pattern: combining patterns

Many medium linked-list problems aren’t new ideas at all. They’re two or three small patterns run one after another. The skill is spotting the pieces.

Pattern

Combining patterns

Template

Use it when: the target shape mixes the front and the back of a list, and you need O(1) space.

Signal words

  • “reorder”
  • “L0 → Ln → L1”
  • “palindrome linked list”
  • “in place”
  • “first and last alternately”

Approach 2: Middle, reverse, merge

  1. Phase 1, find the middle. slow and fast start at the head. While fast can take 2 more steps, move slow 1 and fast 2. slow stops at the end of the first half.
  2. Phase 2, reverse the second half. Cut after the middle (slow.next = null), then reverse the nodes that came after it. prev ends up as the head of the reversed half.
  3. Phase 3, merge alternately. first walks the first half, second the reversed half. Save both nexts, link first → second → (old first.next), and move on. Stop when second runs out.

The bar above the picture tells you which phase is running. In phase 2 the second half drops onto its own row and its arrows flip. In phase 3 it’s redrawn left to right so you can watch the zip zig-zag between the rows. The final step lays the answer out on one row.

Three phases, in place

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

  1. Phase 1 (current): Find the middle
  2. Phase 2: Reverse the second half
  3. Phase 3: Merge, alternating
12345
variables
slow
1node
fast
1node
  • slow / curr / first
  • fast / second
  • First half (waiting)
  • Link just changed
  • Link just cut
  • In its final place

Goal: [1, 2, 3, 4, 5] → first, last, second, second-to-last, ... We do it in 3 phases. Phase 1 finds the middle: slow and fast both start at the head.

Step 1 / 17

Which line is running?

function reorderList(head) {  if (head === null || head.next === null) return;  // Phase 1: find the middleRunning now:   let slow = head;  let fast = head;  while (fast.next !== null && fast.next.next !== null) {    slow = slow.next;    fast = fast.next.next;  }  // Phase 2: reverse the second half  let prev = null;  let curr = slow.next;  slow.next = null; // cut the list in two  while (curr !== null) {    const next = curr.next;    curr.next = prev;    prev = curr;    curr = next;  }  // Phase 3: merge the two halves, alternating  let first = head;  let second = prev;  while (second !== null) {    const tmp1 = first.next;    const tmp2 = second.next;    first.next = second;    second.next = tmp1;    first = tmp1;    second = tmp2;  }}

The code, line by line

Middle, reverse, merge

function reorderList(head) {  if (head === null || head.next === null) return;  // Phase 1: find the middle  let slow = head;  let fast = head;  while (fast.next !== null && fast.next.next !== null) {    slow = slow.next;    fast = fast.next.next;  }  // Phase 2: reverse the second half  let prev = null;  let curr = slow.next;  slow.next = null; // cut the list in two  while (curr !== null) {    const next = curr.next;    curr.next = prev;    prev = curr;    curr = next;  }  // Phase 3: merge the two halves, alternating  let first = head;  let second = prev;  while (second !== null) {    const tmp1 = first.next;    const tmp2 = second.next;    first.next = second;    second.next = tmp1;    first = tmp1;    second = tmp2;  }}
def reorder_list(head):    if head is None or head.next is None:        return    # Phase 1: find the middle    slow, fast = head, head    while fast.next is not None and fast.next.next is not None:        slow = slow.next        fast = fast.next.next    # Phase 2: reverse the second half    prev, curr = None, slow.next    slow.next = None  # cut the list in two    while curr is not None:        nxt = curr.next        curr.next = prev        prev = curr        curr = nxt    # Phase 3: merge the two halves, alternating    first, second = head, prev    while second is not None:        tmp1, tmp2 = first.next, second.next        first.next = second        second.next = tmp1        first, second = tmp1, tmp2

Python returns on its own line (line 3) and assigns pairs on one line (slow, fast = head, head), so the line numbers drift; both are given below. On LeetCode the method is def reorderList(self, head) -> None inside class Solution: it changes the list and returns nothing.

  • JS 2 / Py 2–3: 0 or 1 node: nothing to do. (2 nodes also come out unchanged, and the general code handles them correctly.)
  • JS 5–10 / Py 6–9, phase 1: the loop condition fast.next && fast.next.next stops slow at the first middle for even lengths (2 in [1, 2, 3, 4]). That keeps the first half the same size as, or one bigger than, the second half.
  • JS 13–15 / Py 12–13: curr starts after the middle, and slow.next = null cuts the list in two. Without the cut, the first half would still lead into the second, and phase 3 would build a loop.
  • JS 16–21 / Py 14–18, phase 2: the standard reversal. Afterwards prev is the head of the reversed second half.
  • JS 24–25 / Py 21: first walks the first half, second the reversed second half.
  • JS 26 / Py 22: the second half is never longer than the first, so we stop when it runs out.
  • JS 27–28 / Py 23: save both next nodes before rewiring. This is the “save next first” rule again, twice.
  • JS 29–30 / Py 24–25: slot second in between first and the old first.next.
  • JS 31–32 / Py 26: move both pointers on.

Dry run

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

phasewhat happensfirst halfsecond halfresult so far
1slow 1→2→3, fast 1→3→5; fast.next is null: stopmiddle = 3
2cut after 3; reverse 4 → 51 → 2 → 35 → 4
3first = 1, second = 5: link 1 → 5 → 22 → 341 → 5 → 2
3first = 2, second = 4: link 2 → 4 → 33(empty)1 → 5 → 2 → 4 → 3
donesecond is null: stop1 → 5 → 2 → 4 → 3
head = [1, 2, 3, 4, 5]

Node 3, the middle, never gets touched in phase 3: it was the end of the first half (pointing to null since the cut), and it stays the last node.

Complexity

Array of nodes

Time

O(n)

One pass to copy, one pass of i and j toward each other.

Space

O(n)

The array stores a reference to every node.

Middle, reverse, merge

Time

O(n)

Phase 1 walks half the list, phase 2 reverses half, phase 3 visits every node once: about 2n steps, still O(n).

Space

O(1)

A handful of pointers (slow, fast, prev, curr, first, second, tmp1, tmp2).

Common mistakes and edge cases

What to say out loud:

  1. “The odd positions are the first half in order; the even positions are the second half reversed.”
  2. “So: find the middle with slow/fast, cut, reverse the second half, then merge alternately.”
  3. “Each phase is O(n) time and O(1) space.”
  4. “Edge cases: 0, 1, 2 nodes, and odd vs even length.”
  5. Name the phases before coding; it shows you see the structure.

Likely follow-ups:

  • “Can you do it with a stack instead?” Yes (push all nodes, pop to get the back ones), but that’s O(n) space, like the array.
  • “Check whether a linked list is a palindrome in O(1) space.” (LeetCode 234) Same first two phases, then compare the halves instead of merging.

Related problems: