Turning the rope team

A rope team on a glacier turns back at noon. The order they walked up is exactly the order they cannot walk down.

The problem

A guide's team is roped in a single line. Each climber's rope runs to exactly one other climber, the one behind them, and the climber at the back has nobody behind them. The guide's card lists the team from the lead climber to the tail.

At the turnaround the team has to walk out the way it came, so every rope link must now run the other way and the climber who was at the back becomes the lead. Nobody unclips everyone at once — on a crevassed glacier the team stays linked — and nobody swaps chits. You re-clip one link at a time, holding at most a couple of carabiners.

Return the card as it reads after the turn: the same chit numbers, in the opposite order.

Input. team — a list of integers, the chit numbers from the lead climber to the tail. It may be empty.

Output. A list of the same chit numbers, in the reverse order.

Example.

team = [41, 17, 8, 23]   ->  [23, 8, 17, 41]

Climber 41's rope ran to 17, 17's to 8, 8's to 23. Afterwards 23's rope runs to 8, 8's to 17, 17's to 41, and 41 walks last.

A second example, on the short teams that break careless code:

team = [6]   ->  [6]
team = []    ->  []

A solo climber has no link to flip and an empty card has nothing to hand back; neither may touch a link that does not exist.

Constraints.

• 0 <= len(team) <= 10^5
• 1 <= team[i] <= 10^6
• Chit numbers may repeat — a chit records the hut booking, not the person.
• Extra memory O(1): a fixed number of references, no second card.

Hints

Approach

Brute force

Copy the whole card into a notebook, then work back to front clipping a fresh team together. That is n reads, n writes and n extra slots of storage — at n = 100,000 references, roughly 800 KB of pointers for a job that needs three, and the storage is exactly what the constraint forbids.

The insight

One step of the walk needs exactly three references — the climber behind you, the one you are at, and the one in front — because the assignment that flips a link overwrites the only pointer to the rest of the team.

Save the forward pointer first and the flip is safe. The rope then splits into a reversed front section held by prev and an untouched back section held by cur, and that split is the invariant. Each iteration moves one climber across the boundary, so after n iterations the boundary is past the end and prev holds the whole reversed team.

Algorithm

1. Set prev = None and cur = head.
2. While cur is not None:
3. Save nxt = cur.next before anything else.
4. Flip the link: cur.next = prev.
5. Advance the boundary: prev = cur, then cur = nxt.
6. Return prev — cur is None, and prev is the last climber re-clipped.

Complexity

Time O(n) — one pass, four assignments per climber, nobody visited twice. Space O(1) — three references, whatever the size of the team.

Solution

"""Turning the rope team — iterative pointer reversal with prev, cur and nxt."""


class Climber:
    """One climber; `nxt` is the climber their rope runs to, further back."""

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


def rope_up(chits):
    """Build the team from the card and return the lead climber."""
    lead = None
    for chit in reversed(chits):
        lead = Climber(chit, lead)
    return lead


def read_card(lead):
    """Walk the rope from the lead and write the card back out."""
    chits = []
    while lead:
        chits.append(lead.chit)
        lead = lead.nxt
    return chits


def solve(team):
    prev, cur = None, rope_up(team)
    while cur:
        # invariant: every link before cur has been flipped already,
        # every link from cur on still runs the original way.
        nxt = cur.nxt      # save first: the next line destroys this pointer
        cur.nxt = prev     # flip exactly one link
        prev = cur         # move the boundary one climber along
        cur = nxt
    return read_card(prev)  # cur is None here; prev is the new lead

TESTS = [
    (([41, 17, 8, 23],), [23, 8, 17, 41]),
    (([6],), [6]),
    (([],), []),
    (([5, 5, 5],), [5, 5, 5]),
    (([1000000, 2],), [2, 1000000]),
    ((list(range(1, 201)),), list(range(200, 0, -1))),
]

Pitfalls

• Flipping before saving. Write cur.next = prev and then nxt = cur.next and on the first climber nxt becomes None, because prev started as None. The loop exits immediately and [41, 17, 8, 23] comes back as [41]. It does not crash — it quietly returns a team of one.
• Returning cur. The loop only ends when cur is None, so the caller gets an empty card while the whole team is still roped up behind prev.
• Swapping the two advances. cur = nxt before prev = cur leaves prev and cur on the same climber, and the next iteration writes cur.next = cur. Climber 17 is clipped to their own harness, and any later walk down the rope never reaches the end.

Variants

• Trimming the playout — the same one-pass pointer discipline, but unhooking a node instead of turning every link around.
• Pointer surgery — the lesson behind the three assignments and the order they have to go in.