mafeshsho8lmafeshsho8l
Get Started
All coding questions

Reorder List

medium
NeetCode 150linked-listtwo-pointers

Problem

Given a singly linked list, reorder it so it interleaves the first node, the last node, the second node, the second-to-last node, and so on. Rewire nodes in place without changing their values.

Examples

Input: 1 -> 2 -> 3 -> 4
Output: 1 -> 4 -> 2 -> 3
First and last alternate inward.
Input: 1 -> 2 -> 3 -> 4 -> 5
Output: 1 -> 5 -> 2 -> 4 -> 3
Odd length leaves the middle node last.

Constraints

  • • 1 <= number of nodes <= 5 * 10^4
  • • Reorder in place, no value swaps
Hints(tap to reveal)
  • 1. Find the middle, reverse the second half, then merge.
  • 2. Combine three classic linked-list techniques.
Optimal approach(spoiler)
  1. Locate the midpoint using slow and fast pointers.
  2. Reverse the second half of the list.
  3. Merge the first half and the reversed half by alternating nodes.
  4. Careful pointer bookkeeping avoids breaking the list.
  5. O(n) time, O(1) space.

Ready to solve it?

Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.

Practice in the editor