Show problems as
Classic problem #143MediumLinked ListTwo PointersStackRecursion

Reorder List

Real-world version: Fold the Signal Relay Chain
Tracked in this browser only
Read Reorder List on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstIn-Place Reversal Technique · Linked List, animated step by step

A radio link runs through repeater stations coupled in one direction: each station carries an integer gain and points at the station downstream of it, and the last station points at nothing.

Because the harness passes plain JSON, the link arrives as the array stations, holding the gains from the head station through to the tail station. Your answer takes the same shape: the gains of the recoupled link, head station first.

Re-cable the link so it alternates between the two ends. The head station leads, the tail station follows it, then the second station, then the second-from-last, and so on until every station has been placed exactly once. Only the couplings change: no station is duplicated, dropped, or has its gain rewritten.

Do the work on the couplings themselves rather than by copying gains into a fresh link. Rebuild the stations from the array, then relink them, and beyond those stations and the array you hand back keep only a fixed number of station references.

Examples

Example 1

Input
stations = [2, 6, 1, 9]
Output
[2, 9, 6, 1]

The head station keeps the lead, the tail station couples behind it, then the second station, and the second-from-last station closes the link.

Example 2

Input
stations = [10, 20, 30, 40, 50, 60]
Output
[10, 60, 20, 50, 30, 40]

Three stations from the front interleave with three from the back, so the two halves zip together.

Example 3

Input
stations = [5, 1, 4, 1, 5]
Output
[5, 5, 1, 1, 4]

An odd count leaves one station unpaired, so the middle station with gain 4 ends up at the tail.

Constraints

  • 1 <= stations.length <= 5 * 10^4
  • 1 <= stations[i] <= 1000
  • Beyond the rebuilt stations and the returned array, only a fixed number of station references may be held

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def fold_relay_chain(stations: list[int]) -> list[int]:
Java
public int[] foldRelayChain(int[] stations)

More on the same topics