#20 · Linked List

Reorder List

Rearrange L0 → L1 → … → Ln−1 → Ln into L0 → Ln → L1 → Ln−1 → L2 → … in place, without changing any node values.

MediumLeetCode

Current node
Link just rewired
Done / in result
Marked
Rejected
Dummy head

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Fast and slow pointers

Two pointers walk the same list, one twice as fast. When the fast one reaches the end, the slow one is at the middle: a single pass finds the midpoint without knowing the length.

Memory layout

Two node references; the list is read-only during this phase.

Operation	Cost
find middle	O(n) time, O(1) space

In-place sublist reversal

Reversing the second half turns "reach the last node" from an O(n) walk into an O(1) step: after reversal the second half is read front-to-back in exactly the order the reordered list needs.

Memory layout

Three references (prev, curr, next); only next arrows change.

Operation	Cost
reverse half	O(n) time, O(1) space

Alternating merge of two lists

Take one node from the front list, then one from the reversed back list, re-linking each as you go. Saving both successors before rewriting any arrow is what keeps the lists from tangling.

Memory layout

Two cursors plus two saved successors, all local variables.

Operation	Cost
interleave	O(n) time, O(1) space

Why it fits

The target order pairs the i-th node from the front with the i-th from the back, and a singly linked list can only walk forward. Reversing the back half converts "walk backward" into "walk forward".
Each of the three steps (middle, reverse, interleave) is linear and uses O(1) extra space, so the whole is O(n) time and O(1) space.
Splitting at the middle means the two halves are independent lists, which removes aliasing bugs while rewiring.

Why alternatives degrade

Repeatedly find and move the tail:: Finding the last node costs O(n) each time, giving O(n²) total.
Copy nodes into an array and use indices:: Simple and linear, but O(n) extra memory; the in-place version needs none.
Recursion to reach the end:: Gets the back node "for free" on return but uses O(n) stack and is easy to break on long lists.

Four approaches, from naive to production

1 · beginner

Repeatedly move the last node

time O(n²)space O(1)

For each front node cur, walk to the end of the list, detach the last node and insert it right after cur. Move cur two nodes forward and repeat.

void reorderList(ListNode* head) {
    ListNode* cur = head;
    while (cur && cur->next && cur->next->next) {
        ListNode* prev = cur;
        while (prev->next->next) prev = prev->next;
        ListNode* last = prev->next;
        prev->next = nullptr;
        last->next = cur->next;
        cur->next = last;
        cur = last->next;
    }
    return;
}

public void reorderList(ListNode head) {
    ListNode cur = head;
    while (cur != null && cur.next != null && cur.next.next != null) {
        ListNode prev = cur;
        while (prev.next.next != null) prev = prev.next;
        ListNode last = prev.next;
        prev.next = null;
        last.next = cur.next;
        cur.next = last;
        cur = last.next;
    }
    return;
}

def reorder_list(head):
    cur = head
    while cur and cur.next and cur.next.next:
        prev = cur
        while prev.next.next:
            prev = prev.next
        last = prev.next
        prev.next = None
        last.next = cur.next
        cur.next = last
        cur = last.next
    return

function reorderList(head: ListNode | null): void {
  let cur = head;
  while (cur && cur.next && cur.next.next) {
    let prev = cur;
    while (prev.next!.next) prev = prev.next!;
    const last = prev.next!;
    prev.next = null;
    last.next = cur.next;
    cur.next = last;
    cur = last.next;
  }
  return;
}

Flaws & bottlenecks

Re-walks the remaining list to find the last node every round: n/2 rounds of up to n steps each.
A singly linked list gives no cheap way to reach (or detach) the tail, which is exactly what this code keeps paying for.
Easy to leave a stale arrow: forgetting prev.next = null creates a cycle.

Interviewer cross-questions

What is the time complexity and why?

Say: O(n²): each of about n/2 rounds walks (n − 2·round) nodes to find the tail, which sums to a quadratic number of steps.

How could finding the last node be O(1)?

Say: Keep references to all the nodes (array, O(n) space), or reverse the back half so its nodes are available front-to-back.

Why does the loop condition need cur.next.next?

Say: You can only move the last node behind cur if there are at least two nodes after cur; otherwise the last node is already adjacent (or is cur.next).

2 · intermediate

Array of nodes + two indices

time O(n)space O(n)

Store every node in an array, then link nodes[0] → nodes[n−1] → nodes[1] → nodes[n−2] → … using two indices that converge in the middle.

void reorderList(ListNode* head) {
    if (!head) return;
    vector<ListNode*> nodes;
    for (ListNode* n = head; n; n = n->next) nodes.push_back(n);
    int i = 0;
    int j = (int)nodes.size() - 1;
    while (i < j) {
        nodes[i]->next = nodes[j];
        i++;
        if (i == j) break;
        nodes[j]->next = nodes[i];
        j--;
    }
    nodes[i]->next = nullptr;
    return;
}

public void reorderList(ListNode head) {
    if (head == null) return;
    List<ListNode> nodes = new ArrayList<>();
    for (ListNode n = head; n != null; n = n.next) nodes.add(n);
    int i = 0;
    int j = nodes.size() - 1;
    while (i < j) {
        nodes.get(i).next = nodes.get(j);
        i++;
        if (i == j) break;
        nodes.get(j).next = nodes.get(i);
        j--;
    }
    nodes.get(i).next = null;
    return;
}

def reorder_list(head):
    if not head:
        return
    nodes = []
    n = head
    while n:
        nodes.append(n)
        n = n.next
    i = 0
    j = len(nodes) - 1
    while i < j:
        nodes[i].next = nodes[j]
        i += 1
        if i == j:
            break
        nodes[j].next = nodes[i]
        j -= 1
    nodes[i].next = None
    return

function reorderList(head: ListNode | null): void {
  if (!head) return;
  const nodes: ListNode[] = [];
  for (let n: ListNode | null = head; n; n = n.next) nodes.push(n);
  let i = 0;
  let j = nodes.length - 1;
  while (i < j) {
    nodes[i].next = nodes[j];
    i++;
    if (i === j) break;
    nodes[j].next = nodes[i];
    j--;
  }
  nodes[i].next = null;
  return;
}

Flaws & bottlenecks

Uses O(n) extra memory (one reference per node) when the problem can be solved in O(1).
Needs a careful stop condition: for an even length i and j meet right after i++, and the last next must be set to none or a cycle forms.
Two passes and an array allocation: more cache misses than the in-place approach.

Interviewer cross-questions

Why must the last node's next be set to none?

Say: The node in the middle still points at the node that used to follow it. Without cutting that arrow the reordered list contains a cycle, and any later traversal never ends.

Can you do it with O(1) extra space?

Say: Yes: find the middle with slow/fast pointers, reverse the second half in place, and interleave the halves. That is the next approach.

When would you still prefer the array version?

Say: When memory is not a concern and simplicity matters, since random access by index makes the pairing obvious and hard to get wrong.

3 · advanced

Middle + reverse + interleave

time O(n)space O(1)

Find the middle with slow/fast pointers, cut there, reverse the second half in place, and weave the two lists together one node at a time.

void reorderList(ListNode* head) {
    if (!head || !head->next) return;
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode* prev = nullptr;
    ListNode* curr = slow->next;
    slow->next = nullptr;
    while (curr) {
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    ListNode* first = head;
    ListNode* second = prev;
    while (second) {
        ListNode* t1 = first->next;
        ListNode* t2 = second->next;
        first->next = second;
        second->next = t1;
        first = t1;
        second = t2;
    }
    return;
}

public void reorderList(ListNode head) {
    if (head == null || head.next == null) return;
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode prev = null;
    ListNode curr = slow.next;
    slow.next = null;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    ListNode first = head;
    ListNode second = prev;
    while (second != null) {
        ListNode t1 = first.next;
        ListNode t2 = second.next;
        first.next = second;
        second.next = t1;
        first = t1;
        second = t2;
    }
    return;
}

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

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

Flaws & bottlenecks

Three separate passes, each with its own pointer bookkeeping: easy to get wrong.
Must save both successors before rewriting arrows, or the lists are lost.
Destroys the original order (as required) and cannot be undone without a copy.

Interviewer cross-questions

Why does slow end at the middle?

Say: fast moves twice as fast. When fast reaches the end after k steps, slow has moved k steps, which is about half of the list length.

Why save t1 and t2 before relinking?

Say: first.next = second overwrites the only reference to the rest of the front half, and second.next = t1 overwrites the rest of the back half. Without saved copies those parts would be unreachable.

What happens for even vs odd length?

Say: For odd n the front half has one more node, which ends the list (the last next is already none). For even n both halves match in length. The loop stops when the (shorter) back half runs out.

4 · expert

Guarded, offset-start version

time O(n)space O(1)

The same three phases, hardened: return early for lists of 0–2 nodes, start fast one node ahead so slow always stops at the end of the first half, and detach the halves before reversing.

void reorderList(ListNode* head) {
    if (!head || !head->next || !head->next->next) return;
    ListNode* slow = head;
    ListNode* fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode* prev = nullptr;
    ListNode* curr = slow->next;
    slow->next = nullptr;
    while (curr) {
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    ListNode* a = head;
    ListNode* b = prev;
    while (a && b) {
        ListNode* aNext = a->next;
        ListNode* bNext = b->next;
        a->next = b;
        b->next = aNext;
        a = aNext;
        b = bNext;
    }
    return;
}

public void reorderList(ListNode head) {
    if (head == null || head.next == null || head.next.next == null) return;
    ListNode slow = head;
    ListNode fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode prev = null;
    ListNode curr = slow.next;
    slow.next = null;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    ListNode a = head;
    ListNode b = prev;
    while (a != null && b != null) {
        ListNode aNext = a.next;
        ListNode bNext = b.next;
        a.next = b;
        b.next = aNext;
        a = aNext;
        b = bNext;
    }
    return;
}

def reorder_list(head):
    if not head or not head.next or not head.next.next:
        return
    slow = head
    fast = head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    prev = None
    curr = slow.next
    slow.next = None
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    a = head
    b = prev
    while a and b:
        a_next = a.next
        b_next = b.next
        a.next = b
        b.next = a_next
        a = a_next
        b = b_next
    return

function reorderList(head: ListNode | null): void {
  if (!head || !head.next || !head.next.next) return;
  let slow = head;
  let fast = head.next;
  while (fast && fast.next) {
    slow = slow.next!;
    fast = fast.next.next;
  }
  let prev: ListNode | null = null;
  let curr: ListNode | null = slow.next;
  slow.next = null;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  let a: ListNode | null = head;
  let b = prev;
  while (a && b) {
    const aNext = a.next;
    const bNext = b.next;
    a.next = b;
    b.next = aNext;
    a = aNext;
    b = bNext;
  }
  return;
}

Flaws & bottlenecks

Still mutates the list in place and is not safe for concurrent readers: intermediate states are visible.
No guard against a cyclic input list: slow/fast would meet but this code would not terminate correctly. Production code might run a cycle check first.
Correctness depends on the invariant "first half is never shorter than the second", which only holds because of the fast = head.next offset.

Interviewer cross-questions

Why start fast at head.next?

Say: With the offset, slow stops at the last node of the first half for both odd and even lengths (for 4 nodes it stops on the 2nd, for 5 on the 3rd). The first half is therefore never shorter than the second, and the interleave loop can stop as soon as the back half is empty.

Why detach before reversing?

Say: Setting slow.next to none makes the two halves independent lists. The reverse loop then ends naturally at the end of the back half, and the first half cannot be reached by accident through the reversed arrows.

How would you test this?

Say: Lengths 0, 1, 2, 3, 4, 5 and a large list, checking both the value order and that the final node points at nothing (and that traversal terminates).

Synchronized code walkthrough

Showing: Repeatedly move the last node — shares the player above; click any step to jump.

void reorderList(ListNode* head) {
    ListNode* cur = head;
    while (cur && cur->next && cur->next->next) {
        ListNode* prev = cur;
        while (prev->next->next) prev = prev->next;
        ListNode* last = prev->next;
        prev->next = nullptr;
        last->next = cur->next;
        cur->next = last;
        cur = last->next;
    }
    return;
}

public void reorderList(ListNode head) {
    ListNode cur = head;
    while (cur != null && cur.next != null && cur.next.next != null) {
        ListNode prev = cur;
        while (prev.next.next != null) prev = prev.next;
        ListNode last = prev.next;
        prev.next = null;
        last.next = cur.next;
        cur.next = last;
        cur = last.next;
    }
    return;
}

def reorder_list(head):
    cur = head
    while cur and cur.next and cur.next.next:
        prev = cur
        while prev.next.next:
            prev = prev.next
        last = prev.next
        prev.next = None
        last.next = cur.next
        cur.next = last
        cur = last.next
    return

function reorderList(head: ListNode | null): void {
  let cur = head;
  while (cur && cur.next && cur.next.next) {
    let prev = cur;
    while (prev.next!.next) prev = prev.next!;
    const last = prev.next!;
    prev.next = null;
    last.next = cur.next;
    cur.next = last;
    cur = last.next;
  }
  return;
}

void reorderList(ListNode* head) {
    if (!head) return;
    vector<ListNode*> nodes;
    for (ListNode* n = head; n; n = n->next) nodes.push_back(n);
    int i = 0;
    int j = (int)nodes.size() - 1;
    while (i < j) {
        nodes[i]->next = nodes[j];
        i++;
        if (i == j) break;
        nodes[j]->next = nodes[i];
        j--;
    }
    nodes[i]->next = nullptr;
    return;
}

public void reorderList(ListNode head) {
    if (head == null) return;
    List<ListNode> nodes = new ArrayList<>();
    for (ListNode n = head; n != null; n = n.next) nodes.add(n);
    int i = 0;
    int j = nodes.size() - 1;
    while (i < j) {
        nodes.get(i).next = nodes.get(j);
        i++;
        if (i == j) break;
        nodes.get(j).next = nodes.get(i);
        j--;
    }
    nodes.get(i).next = null;
    return;
}

def reorder_list(head):
    if not head:
        return
    nodes = []
    n = head
    while n:
        nodes.append(n)
        n = n.next
    i = 0
    j = len(nodes) - 1
    while i < j:
        nodes[i].next = nodes[j]
        i += 1
        if i == j:
            break
        nodes[j].next = nodes[i]
        j -= 1
    nodes[i].next = None
    return

function reorderList(head: ListNode | null): void {
  if (!head) return;
  const nodes: ListNode[] = [];
  for (let n: ListNode | null = head; n; n = n.next) nodes.push(n);
  let i = 0;
  let j = nodes.length - 1;
  while (i < j) {
    nodes[i].next = nodes[j];
    i++;
    if (i === j) break;
    nodes[j].next = nodes[i];
    j--;
  }
  nodes[i].next = null;
  return;
}

void reorderList(ListNode* head) {
    if (!head || !head->next) return;
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode* prev = nullptr;
    ListNode* curr = slow->next;
    slow->next = nullptr;
    while (curr) {
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    ListNode* first = head;
    ListNode* second = prev;
    while (second) {
        ListNode* t1 = first->next;
        ListNode* t2 = second->next;
        first->next = second;
        second->next = t1;
        first = t1;
        second = t2;
    }
    return;
}

public void reorderList(ListNode head) {
    if (head == null || head.next == null) return;
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode prev = null;
    ListNode curr = slow.next;
    slow.next = null;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    ListNode first = head;
    ListNode second = prev;
    while (second != null) {
        ListNode t1 = first.next;
        ListNode t2 = second.next;
        first.next = second;
        second.next = t1;
        first = t1;
        second = t2;
    }
    return;
}

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

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

void reorderList(ListNode* head) {
    if (!head || !head->next || !head->next->next) return;
    ListNode* slow = head;
    ListNode* fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode* prev = nullptr;
    ListNode* curr = slow->next;
    slow->next = nullptr;
    while (curr) {
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    ListNode* a = head;
    ListNode* b = prev;
    while (a && b) {
        ListNode* aNext = a->next;
        ListNode* bNext = b->next;
        a->next = b;
        b->next = aNext;
        a = aNext;
        b = bNext;
    }
    return;
}

public void reorderList(ListNode head) {
    if (head == null || head.next == null || head.next.next == null) return;
    ListNode slow = head;
    ListNode fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode prev = null;
    ListNode curr = slow.next;
    slow.next = null;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    ListNode a = head;
    ListNode b = prev;
    while (a != null && b != null) {
        ListNode aNext = a.next;
        ListNode bNext = b.next;
        a.next = b;
        b.next = aNext;
        a = aNext;
        b = bNext;
    }
    return;
}

def reorder_list(head):
    if not head or not head.next or not head.next.next:
        return
    slow = head
    fast = head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    prev = None
    curr = slow.next
    slow.next = None
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    a = head
    b = prev
    while a and b:
        a_next = a.next
        b_next = b.next
        a.next = b
        b.next = a_next
        a = a_next
        b = b_next
    return

function reorderList(head: ListNode | null): void {
  if (!head || !head.next || !head.next.next) return;
  let slow = head;
  let fast = head.next;
  while (fast && fast.next) {
    slow = slow.next!;
    fast = fast.next.next;
  }
  let prev: ListNode | null = null;
  let curr: ListNode | null = slow.next;
  slow.next = null;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  let a: ListNode | null = head;
  let b = prev;
  while (a && b) {
    const aNext = a.next;
    const bNext = b.next;
    a.next = b;
    b.next = aNext;
    a = aNext;
    b = bNext;
  }
  return;
}