Skip to main content

143. Reorder List

medium

Reorder a linked list so the order becomes first, last, second, second-to-last, third, third-to-last, etc. The three-phase decomposition (find middle, reverse second half, merge) tests pointer fluency.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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 in the 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.

Constraints

  • The number of nodes in the list is in the range [1, 5 * 10^4].
  • 1 <= Node.val <= 1000

Examples

Example 1

Input
head = [1,2,3,4]
Output
[1,4,2,3]

Example 2

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Brute force: convert to array, two-pointer reorder. Works but uses O(n) extra space.

Hint 2

For O(1) space, decompose into three passes: find the middle, reverse the second half, then weave the two halves together.

Hint 3

Use slow/fast to find the middle; reverse from slow.next using the standard three-pointer reversal; then interleave by alternating next pointers.

Solution approach

Reveal approach

Three-phase O(1)-space approach. (1) Find the middle using slow/fast pointers — slow lands on the midpoint at the end. (2) Reverse the linked list starting at slow.next, then set slow.next = null to split the list into two halves. (3) Merge the two halves: at each step, save the next nodes of both lists, then rewire to interleave (first.next = second; second.next = savedFirstNext) and advance both pointers. The result is the reordered list in place. O(n) time, O(1) extra space.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • linked-list
  • two-pointers
  • reversal

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Meta

Practice these live with InterviewChamp.AI

Drill Reorder List and Linked Lists problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →