0059EasyLinked ListRecursion

Rewind the Telemetry 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 probe stores its telemetry as a one-way chain of frames: every frame carries a signed reading and a link to the frame recorded after it, and the final frame links to nothing.

Because the harness passes plain JSON, the chain reaches you as the array frames, holding the readings in order from the front frame to the last one. An empty array means the chain has no frames at all. Your answer must use the same shape: the readings of the rebuilt chain, front frame first.

Turn the chain around so the frame that was last becomes the front and every link points at the frame that used to precede it. Solve it the way the chain itself demands: rebuild the frames, then walk them once and redirect one link at a time, carrying the frame behind you as you go. Beyond the frames themselves and the array you return, only a fixed number of frame references may be held.

Examples

Example 1

Input: frames = [4, -1, 9, 9, -12]
Output: [-12, 9, 9, -1, 4]

The frame holding -12 was last, so it becomes the front, and the readings come back in the opposite order. Repeated readings keep both copies.

Example 2

Input: frames = [30, -30]
Output: [-30, 30]

With two frames the single link between them flips, so the second frame leads.

Example 3

Input: frames = [7]
Output: [7]

A lone frame has no link to redirect, so the chain comes back unchanged. A chain of zero frames likewise answers with an empty chain.

Constraints

0 <= frames.length <= 5000
-5000 <= frames[i] <= 5000

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 rewind_telemetry_chain(frames: list[int]) -> list[int]:

Java

public int[] rewindTelemetryChain(int[] frames)

The intended approach

Time O(n)Space O(n) for the chain of frames built from the input, plus O(1) frame references beyond it

Materialise the chain of frame objects from the array, then walk it once holding three references: the frame already turned around, the frame being handled, and the one after it. Grab the next link before overwriting it, point the current frame at the frame behind it, and shuffle all three references forward. When the walk falls off the end, the frame last handled is the new front, and reading its links out gives the answer.

Pythonentry point: rewind_telemetry_chain

def rewind_telemetry_chain(frames):
    class Frame:
        __slots__ = ("reading", "nxt")

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

    head = None
    tail = None
    for reading in frames:
        node = Frame(reading)
        if head is None:
            head = node
        else:
            tail.nxt = node
        tail = node
    prev = None
    cur = head
    while cur is not None:
        nxt = cur.nxt
        cur.nxt = prev
        prev = cur
        cur = nxt
    out = []
    node = prev
    while node is not None:
        out.append(node.reading)
        node = node.nxt
    return out

The obvious version

Recursive: reverse everything after the front frame, then append the front frame behind it. Each level copies the remaining readings, so O(n^2).

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_rewind_chain(frames):
    if not frames:
        return []
    return bf_rewind_chain(frames[1:]) + [frames[0]]

How this problem was checked

Reference solution executed against 8 test cases — 8 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