loading

Reorder List — Step-by-Step Visualization

mediumLeetCode #143Linked ListTwo PointersStackRecursion

You are given the head of a singly linked-list. The list can be represented as: `L0 → L1 → … → Ln - 1 → Ln`. Reorder the list to be on the following form: `L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …`. You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Algorithm Pattern

Linked List Multi-Phase Manipulation

Key Idea

Reordering requires connecting the first node to the last, then to the second, then to the second-to-last, and so on. We can achieve this in $O(n)$ time using three steps: 1. Find the middle of the list. 2. Reverse the second half. 3. Merge the two halves by alternating nodes.

Step-by-Step Approach

  1. Find the middle using fast and slow pointers.
  2. Split the list into two: `head` and `second` (starting from `middle.next`).
  3. Reverse the `second` half in-place.
  4. Merge: Alternate between nodes from the first half and the reversed second half.

Common Gotchas

  • Don't forget to set `middle.next = None` to terminate the first half.
  • Reversing a linked list requires tracking `prev`, `curr`, and `next` pointers carefully.

Related Problems

← All problems