Reverse a Singly Linked List

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

Algorithm

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

Basic Implementation

basic.pl

use strict; use warnings;

sub add_node {
	my ($nodes_ref, $value, $next_idx) = @_;
	my $idx = scalar @$nodes_ref;
	push @$nodes_ref, { value => $value, next_idx => $next_idx };
	return $idx;
}

my @nodes = ();
my $n5 = add_node(\@nodes, 5, -1);
my $n4 = add_node(\@nodes, 4, $n5);
my $n3 = add_node(\@nodes, 3, $n4);
my $n2 = add_node(\@nodes, 2, $n3);
my $head = add_node(\@nodes, 1, $n2);

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

Complexity

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

Implementation notes

Perl: same three-pointer pattern as the other languages, but each pointer is an integer index into the @nodes arena of hash references (-1 is the sentinel). The arena avoids the blessed-reference dance the classic OO 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 because Perl's reference counting only frees a node when nothing references it.
add_node receives a reference to the arena (\@nodes) and grows it in place via push @$nodes_ref, ..., so the call mutates the shared arena the way the lesson spec models it.
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 `$nodes[$cursor]->{next_idx}` from forward (toward `$next_idx`) to backward (toward `$prev`).