0097HardLinked ListRecursion

Shunting Wagon Blocks

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 rail yard holds one chain of coupled wagons. The chain is handed to you as wagons, the list of wagon numbers read from the locomotive end to the far end, so wagons[0] is coupled closest to the locomotive and each wagon is coupled only to its neighbours.

The shunter works from the locomotive end and takes the chain in consecutive blocks of k wagons. Every block that is complete gets turned around, so its wagons come back coupled in the opposite order while the block stays where it was in the chain. If fewer than k wagons remain at the far end, that leftover stretch is left exactly as it is.

Re-couple the wagons where they stand: rearrange wagons in place, using only a constant amount of extra space beyond the input, then return it. Wagon numbers may repeat, since two wagons can carry the same load code.

Examples

Example 1

Input: wagons = [7, 2, 9, 4, 5, 6], k = 3
Output: [9, 2, 7, 6, 5, 4]

The first block holds 7, 2, 9 and comes back as 9, 2, 7. The second holds 4, 5, 6 and comes back as 6, 5, 4.

Example 2

Input: wagons = [3, 1, 4, 1, 5, 9, 2], k = 5
Output: [5, 1, 4, 1, 3, 9, 2]

Only one complete block of five exists, so it is turned around. The remaining stretch 9, 2 is too short to shunt and keeps its coupling.

Example 3

Input: wagons = [4, 4, 9], k = 1
Output: [4, 4, 9]

Blocks of one wagon come back the way they went in, so the chain is unchanged.

Constraints

n is the number of wagons in the chain
1 <= k <= n <= 5000
0 <= wagons[i] <= 1000
The rearrangement must happen in place, using O(1) extra space beyond the input

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 shunt_blocks(wagons: list[int], k: int) -> list[int]:

Java

public int[] shuntBlocks(int[] wagons, int k)

The intended approach

Time O(n)Space O(1)

Walk the chain in strides of `k` and only shunt a block once its far end is known to exist, which is what keeps the short leftover stretch untouched. Each complete block is turned around by trading the wagon at its near end with the wagon at its far end and stepping both ends inward until they meet, so nothing is copied out of the chain and only two position markers are held.

Pythonentry point: shunt_blocks

def shunt_blocks(wagons, k):
    total = len(wagons)
    start = 0
    while start + k <= total:
        near = start
        far = start + k - 1
        while near < far:
            wagons[near], wagons[far] = wagons[far], wagons[near]
            near += 1
            far -= 1
        start += k
    return wagons

The obvious version

Cut the chain into fresh slices of length k, flip each full slice with a library reversal, append the leftover untouched, and hand back the rebuilt list. Ignores the in-place requirement on purpose.

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_shunt_blocks(wagons, k):
    rebuilt = []
    total = len(wagons)
    cut = 0
    while cut + k <= total:
        block = list(wagons[cut:cut + k])
        block.reverse()
        rebuilt.extend(block)
        cut += k
    rebuilt.extend(wagons[cut:])
    return rebuilt

How this problem was checked

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