Reverse a Linked List

core

A singly linked list is given here without node objects: nodes are numbered 0 through n-1, next[u] holds the index of the node after u or -1 when u is the last node, and head is the index of the first node. A node's position in the array means nothing, only the links do: the list order is whatever chain the next values trace out from head, and every one of the n nodes sits on that chain exactly once. The list always has at least one node, so head is always a valid index.

Implement reverse_list(next, head): rewire the links in place so the list runs in the opposite direction, and return the index of the new head (the old tail). The starter hands you the loop; the drill is the rotation inside it, and the order of those lines is the whole game. Save curr's successor before you overwrite next[curr], point next[curr] back at prev, then advance prev and curr. Overwrite first and the one link you still needed is gone: curr = next[curr] now reads the link you just rewired, so the walk stops after a single step instead of reaching the rest of the list. The checker walks the array you were given after your function returns, starting at the index you return, so building a fresh array instead of rewiring this one will not pass.

Example: with next = {2, -1, 1} and head = 0, the list is 0 -> 2 -> 1. reverse_list returns 1 and leaves next = {-1, 2, 0}: the reversed list is 1 -> 2 -> 0, so next[1] = 2, next[2] = 0, and node 0, now the tail, gets next[0] = -1.

Input format: each test in tests/*.in is laid out as:

Line 1: n, the number of nodes; nodes are numbered 0 to n - 1.
Line 2: the n entries of next, where the i-th is the index node i points to, or -1 for the last node.
Line 3: head, the index of the first node.

Test 03.in reads:

3
2 -1 1
0

This is 3 nodes stored out of order: starting at head = 0, the list runs 0 -> 2 (since next[0] = 2), then 2 -> 1 (next[2] = 1), and next[1] = -1 ends it. The list order is 0, 2, 1, not the storage order.

Where you'll use it:

✦ Solution & editorial unlock with the pass.