Linked Structures

Reverse a Singly Linked List

Walk the list with three pointers: prev, cursor, and next. Each iteration saves cursor.next, re-points cursor.next backward to prev, then advances prev = cursor; cursor = next.

Algorithm

Canonical input 1 -> 2 -> 3 -> 4 -> 5 -> null reverses to 5 -> 4 -> 3 -> 2 -> 1 -> null after five rewire frames.

Basic Implementation

basic.php 
<?php
function add_node(&$nodes, $value, $next_idx) {
	$idx = count($nodes);
	$nodes[] = ["value" => $value, "next_idx" => $next_idx];
	return $idx;
}

$nodes = [];
$n5 = add_node($nodes, 5, -1);
$n4 = add_node($nodes, 4, $n5);
$n3 = add_node($nodes, 3, $n4);
$n2 = add_node($nodes, 2, $n3);
$head = add_node($nodes, 1, $n2);

$prev = -1;
$cursor = $head;
while ($cursor != -1) {
	$next_idx = $nodes[$cursor]["next_idx"];
	$nodes[$cursor]["next_idx"] = $prev;
	$prev = $cursor;
	$cursor = $next_idx;
}
$head = $prev;
$cur = $head;
while ($cur != -1) {
	echo $nodes[$cur]["value"] . " -> ";
	$cur = $nodes[$cur]["next_idx"];
}
echo "null\n";

Complexity

  • Time: O(n)
  • Space: O(1)

Implementation notes

  • PHP: same three-pointer pattern as the other languages, but each pointer is an int index into the $nodes arena (-1 is the sentinel). The arena avoids the ?Node ownership dance the classic reference idiom requires while keeping the algorithm visible.
  • $head = $prev; at the end re-points the head at the old tail; the arena keeps every node alive throughout the reversal.
  • add_node takes &$nodes by reference so the arena grows in-place without copy-on-write surprises, mirroring how the lesson spec treats the arena as shared mutable state.
  • The replay shows all three pointers each frame and a distinct rewire frame between save and advance, with node(<value>) labels instead of runtime references.
three pointers `$prev` starts `-1`, `$cursor` starts at `$head`, `$next_idx` is the saved forward link.
rewire The rewire frame flips `$cursor.next_idx` from forward (toward `next`) to backward (toward `prev`).