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

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

Basic Implementation

basic.rb 
ListNode = Struct.new(:value, :next_idx)

def add_node(nodes, value, next_idx)
	idx = nodes.length
	nodes << ListNode.new(value, next_idx)
	idx
end

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
end
head = prev
cur = head
while cur != -1
	print "#{nodes[cur].value} -> "
	cur = nodes[cur].next_idx
end
puts "nil"

Complexity

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

Implementation notes

  • Ruby: same three-pointer pattern as the other languages, but each pointer is an Integer index into the Array arena of ListNode structs (-1 is the sentinel). The arena avoids the recursive class-reference dance the classic 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.
  • 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_idx`) to backward (toward `prev`).