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 Sam K., 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

More Linked Lists practice problems

See all Linked Lists problems →