0137MediumLinked ListTwo PointersStackRecursion

Fold the Signal Relay Chain

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def fold_relay_chain(stations: list[int]) -> list[int]:

Java

public int[] foldRelayChain(int[] stations)

The intended approach

Time O(n)Space O(n) for the stations rebuilt from the input, plus O(1) station references beyond them

Rebuild the stations, then find the split point by advancing one reference a station at a time and another two at a time, so the fast one falls off the end as the slow one reaches the last station of the front half. Cut the link there, turn the back half around by redirecting one coupling at a time, and finally zip the two halves by alternately splicing a back station behind a front station, saving each successor before overwriting the coupling.

Pythonentry point: fold_relay_chain

def fold_relay_chain(stations):
    class Station:
        __slots__ = ("gain", "nxt")

        def __init__(self, gain):
            self.gain = gain
            self.nxt = None

    head = None
    tail = None
    for gain in stations:
        node = Station(gain)
        if head is None:
            head = node
        else:
            tail.nxt = node
        tail = node
    slow = head
    fast = head
    while fast.nxt is not None and fast.nxt.nxt is not None:
        slow = slow.nxt
        fast = fast.nxt.nxt
    back = slow.nxt
    slow.nxt = None
    prev = None
    while back is not None:
        nxt = back.nxt
        back.nxt = prev
        prev = back
        back = nxt
    front = head
    back = prev
    while back is not None:
        front_next = front.nxt
        back_next = back.nxt
        front.nxt = back
        back.nxt = front_next
        front = front_next
        back = back_next
    out = []
    node = head
    while node is not None:
        out.append(node.gain)
        node = node.nxt
    return out

The obvious version

Read the gains straight off the input by index, taking one from the front and one from the back in turn and appending the odd station last. No relinking at all.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_fold_chain(stations):
    lo = 0
    hi = len(stations) - 1
    out = []
    while lo < hi:
        out.append(stations[lo])
        out.append(stations[hi])
        lo += 1
        hi -= 1
    if lo == hi:
        out.append(stations[lo])
    return out

How this problem was checked

Reference solution executed against 9 test cases — 9 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in