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.lua

local function add_node(nodes, value, next_idx)
	local idx = #nodes + 1
	nodes[idx] = {value = value, next_idx = next_idx}
	return idx
end

local nodes = {}
local n5 = add_node(nodes, 5, -1)
local n4 = add_node(nodes, 4, n5)
local n3 = add_node(nodes, 3, n4)
local n2 = add_node(nodes, 2, n3)
local head = add_node(nodes, 1, n2)

local prev = -1
local cursor = head
while cursor ~= -1 do
	local next_idx = nodes[cursor].next_idx
	nodes[cursor].next_idx = prev
	prev = cursor
	cursor = next_idx
end
head = prev
local cur = head
while cur ~= -1 do
	io.write(tostring(nodes[cur].value) .. " -> ")
	cur = nodes[cur].next_idx
end
io.write("null\n")

Complexity

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

Implementation notes

Lua: same three-pointer pattern as the other languages, but each pointer is an integer 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 receives the arena as a parameter and grows it in place; Lua passes tables by reference, 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 `cursor.next_idx` from forward (toward `next`) to backward (toward `prev`).