Show problems as
Classic problem #2074MediumLinked List

Reverse Nodes in Even Length Groups

Real-world version: Railcar Chain Group Flips
Tracked in this browser only
Read Reverse Nodes in Even Length Groups on LeetCode(opens in a new tab)

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

A shunting yard holds one chain of coupled railcars. The chain reaches you as a list cars of car weights in order from the locomotive end to the tail, so cars[0] is the car coupled straight behind the locomotive and each following entry is the next car back.

Starting at the locomotive end, the chain is carved into consecutive groups. The first group takes 1 car, the second takes 2 cars, the third takes 3, and each group after that takes one more car than the group before it. The final group takes whatever cars are still left, which can be fewer than its turn calls for.

Every group holding an even number of cars has its cars put back in the opposite order, within the same stretch of the chain. Groups holding an odd number of cars are left as they are. Group boundaries never move, and no car ever leaves the group it landed in.

Return the weights of the chain in the resulting order. Do the rearranging by uncoupling and recoupling cars inside the chain rather than by building a fresh chain alongside it, and use only a constant amount of extra space beyond the chain itself.

Examples

Example 1

Input
cars = [40, 7, 19, 5, 26, 12, 33]
Output
[40, 19, 7, 5, 26, 12, 33]

The groups hold 1, 2, 3 and 1 cars, so only the pair 7 and 19 changes places; the group of three and the lone car at the tail stay as they were.

Example 2

Input
cars = [4, 9, 2, 6, 1]
Output
[4, 2, 9, 1, 6]

The groups hold 1, 2 and 2 cars, because only two cars are left for the third group; both pairs change places.

Example 3

Input
cars = [61, 14, 88, 3, 47, 20, 75, 9, 52, 36, 28, 66]
Output
[61, 88, 14, 3, 47, 20, 36, 52, 9, 75, 66, 28]

The groups hold 1, 2, 3, 4 and 2 cars; the groups of two and of four are put back in the opposite order and the groups of one and three are untouched.

Constraints

  • 1 <= cars.length <= 10^5
  • 0 <= cars[i] <= 10^5

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 flip_even_groups(cars: list[int]) -> list[int]:
Java
public int[] flipEvenGroups(int[] cars)

More on the same topics