Linked Structures

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

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";

The three-pointer loop saves the forward link, flips one next pointer, then advances prev and cursor.

Step 1 - Save the first forward link

prev starts at null, cursor is node(1), and nxt saves node(2).

Initial 1 -> 2 -> 3 -> 4 -> 5 chain with prev, cursor, and nxt named.prevcursornxtnullnode(1)node(2)node(3)node(4)node(5)

Step 2 - Flip node(1)

Set node(1).next to prev, making the reversed prefix 1 -> null.

After the first flip, prev points at node(1) and cursor advances to node(2).prevcursornode(1)nullnode(2)node(3)node(4)node(5)

Step 3 - Reversed prefix reaches 3

After three flips, the prefix is 3 -> 2 -> 1 -> null and cursor is node(4).

Middle of the reverse: prefix 3 -> 2 -> 1, suffix 4 -> 5.prevcursornode(3)node(2)node(1)nullnode(4)node(5)

Step 4 - Done

When cursor reaches null, prev is the new head: 5 -> 4 -> 3 -> 2 -> 1 -> null.

Final reversed list.headnode(5)node(4)node(3)node(2)node(1)null

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`).