Skip to content

Volume ITechnology

4.9.3 — Reorder List ​

LeetCode 143 · Medium · ★ Blind 75

The problem ​

You are given the head of a linked list L_0 \to L_1 \to \dots \to L_n. Rearrange it into L_0 \to L_n \to L_1 \to L_{n-1} \to L_2 \to \dots. In words: the first node, then the last node, then the second node, then the second-to-last, and so on. You must re-link the nodes themselves, not just swap their values. Nothing is returned; the list is changed in place.

1 → 2 → 3 → 4        becomes   1 → 4 → 2 → 3
1 → 2 → 3 → 4 → 5    becomes   1 → 5 → 2 → 4 → 3

The list has between 1 and 50,000 nodes.

What the problem is really asking ​

Imagine folding the list in half like a strip of paper, so the end lands on top of the start, and then reading the layers alternately.

The trouble is that the target order needs the last node second, the second-to-last fourth, and so on. A singly linked list can only be walked forwards. There is no cheap way to reach the back.

So the real question is: how do you make the back half of the list reachable from the front? The answer is to reverse it.

The brute force, and where it wastes work ​

Without extra memory, the direct approach is: take the first node, walk the whole list to find the last node, link them, then repeat from the second node.

Finding the last node takes about n steps, the second-to-last n - 1, and so on. That adds up to about \frac{n^2}{2} steps, over a billion for 50,000 nodes.

The waste in one sentence: it walks almost the whole list again every time it needs the next node from the back.

The idea ​

Three techniques you have already met, used one after another.

  1. Find the middle with a slow pointer and a fast pointer.
  2. Reverse the second half, using the loop from 4.9.1. Now the back of the list can be walked starting from its last node.
  3. Weave the two halves together, taking one node from each in turn.
1 → 2 → 3 → 4 → 5 → 6

split:     1 → 2 → 3        4 → 5 → 6
reverse:   1 → 2 → 3        6 → 5 → 4
weave:     1 → 6 → 2 → 5 → 3 → 4

Finding the middle with two speeds ​

Start two pointers at the head. Move slow one node per step and fast two nodes per step. When fast reaches the end, slow has gone exactly half as far, so it is at the middle.

python
slow, fast = head, head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

On a list with an even number of nodes there are two middles. This loop stops slow on the second one. For 1 → 2 → 3 → 4, slow ends on node 3. The second half is then everything after slow, which is just node 4. That leaves the first half one node longer than the second half or the same length, which is what the weave needs.

Do not memorise which middle you get. Trace a four-node list in your head before you commit. It takes five seconds, and it removes the most common source of off-by-one bugs in linked-list problems.

The solution ​

python
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        if not head or not head.next:                     # (1)
            return

        slow, fast = head, head                           # (2)
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        second = slow.next                                # (3)
        slow.next = None                                  # (4)

        prev = None                                       # (5)
        while second:
            nxt = second.next
            second.next = prev
            prev = second
            second = nxt
        second = prev                                     # (6)

        first = head                                      # (7)
        while second:                                     # (8)
            f_next, s_next = first.next, second.next      # (9)
            first.next = second                           # (10)
            second.next = f_next                          # (11)
            first, second = f_next, s_next                # (12)
ts
function reorderList(head: ListNode | null): void {
  if (!head || !head.next) return;                        // (1)

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

  let second = slow.next;                                 // (3)
  slow.next = null;                                       // (4)

  let prev: ListNode | null = null;                       // (5)
  while (second) {
    const nxt: ListNode | null = second.next;
    second.next = prev;
    prev = second;
    second = nxt;
  }
  second = prev;                                          // (6)

  let first: ListNode | null = head;                      // (7)
  while (second) {                                        // (8)
    const fNext = first!.next, sNext: ListNode | null = second.next;  // (9)
    first!.next = second;                                 // (10)
    second.next = fNext;                                  // (11)
    first = fNext;                                        // (12)
    second = sNext;
  }
}

Line by line ​

(1) Lists of 0 or 1 node are already in the right order.

(2) Find the middle. slow moves one step, fast moves two. The loop stops when fast has no room for two more steps. As explained above, slow ends on the middle node, or the second of two middles.

(3) The second half starts just after slow.

(4) Cut the list in two. This is the line people forget. Without it, the last node of the first half still points into the second half. After step 2 reverses the second half, that leftover pointer creates a loop, and the list never ends. The two halves must be fully separated before they are woven.

(5) Reverse the second half. This is exactly the loop from 4.9.1: save the next node, turn the arrow back, step forward.

(6) prev is the head of the reversed second half, which was the last node of the original list.

(7) first walks the first half from the original head.

(8) Loop while the second half has nodes. The second half is never longer than the first, so it always runs out first. If we looped on first instead, the last step would try to read .next from None and crash.

(9) Save both next nodes. The moment line (10) runs, the old first.next is overwritten. Same rule as reversing: save the way forward before you change a pointer.

(10) The first-half node points to the second-half node.

(11) The second-half node points to the next first-half node.

(12) Step both forward to the saved nodes.

Trace ​

Take 1 → 2 → 3 → 4.

Step 1, find the middle. slow ends on node 3.

Steps 3 and 4, cut. second is node 4. Node 3 now points to None. The halves are 1 → 2 → 3 and 4.

Step 5, reverse. A single node reversed is still 4.

Step 8 onwards, weave.

RoundfirstsecondSaved f_next, s_nextLinks made
1142, None1 → 4, 4 → 2
22None—loop ends

Node 2 still points to node 3, and node 3 points to None. The result is 1 → 4 → 2 → 3. ✓

Now 1 → 2 → 3 → 4 → 5. slow ends on 3. The halves are 1 → 2 → 3 and 4 → 5, reversed to 5 → 4. The weave makes 1 → 5 → 2 → 4 → 3. ✓

Complexity, derived ​

Time. Finding the middle walks about n/2 steps. Reversing the second half walks about n/2 nodes. Weaving walks about n/2 rounds. That is about 1.5n steps in total, which is O(n).

Space. A handful of pointer variables, no lists and no recursion. So the extra memory is O(1).

The easy alternative ​

Put every node into an array, then walk it from both ends and re-link.

python
nodes = []
node = head
while node:
    nodes.append(node)
    node = node.next

i, j = 0, len(nodes) - 1
while i < j:
    nodes[i].next = nodes[j]      # front points to back
    i += 1
    if i == j:
        break
    nodes[j].next = nodes[i]      # back points to the next front
    j -= 1
nodes[i].next = None              # the last node in the new order ends the list

This is O(n) time and O(n) memory. It is much easier to get right. It is a perfectly good first answer if you say the memory cost out loud and then offer the O(1) version as the improvement.

Edge cases ​

  • One node. Line (1) returns.
  • Two nodes, like 1 → 2. slow ends on 2, the second half is empty, and the list stays 1 → 2, which is correct.
  • Three nodes, like 1 → 2 → 3. slow ends on 2. The halves are 1 → 2 and 3. The weave makes 1 → 3 → 2.

Variations you will meet ​

The three pieces here are the whole toolkit for this chapter.

  • Palindrome Linked List. Find the middle, reverse the second half, and compare the two halves node by node.
  • Sort List. Find the middle, sort each half, and merge them with 4.9.2. That is merge sort on a list.
  • Split Linked List in Parts. Cut a list into k nearly equal pieces.

The general lesson: a singly linked list cannot be walked backwards, so when a problem needs the back, reverse that part.

What the interviewer will push on ​

"Why do you cut the list at the middle?" Otherwise the first half still points into the second half, and reversing creates a loop.

"Which middle does your loop find?" Know it, and prove it by tracing a four-node list.

"Why does the weave loop on the second half?" It is never longer, so it always finishes first.

"Can you do it without extra memory?" Yes, this version. Offer the array version first, since it is easier, then improve it.

One thing to volunteer: name the three steps before you write any code: "find the middle, reverse the second half, weave". Then write them one at a time. This problem punishes people who start typing before they have the plan.

Next: 4.9.4 Remove Nth Node From End of List. Two pointers again, but now with a fixed gap between them.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet