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 -> nil reverses to 5 -> 4 -> 3 -> 2 -> 1 -> nil after five rewire frames.

Basic Implementation

basic.rs

struct ListNode {
	value: i32,
	next: Option<usize>,
}

fn add_node(nodes: &mut Vec<ListNode>, value: i32, next: Option<usize>) -> usize {
	let idx = nodes.len();
	nodes.push(ListNode { value, next });
	idx
}

fn main() {
	let mut nodes: Vec<ListNode> = Vec::new();
	let n5 = add_node(&mut nodes, 5, None);
	let n4 = add_node(&mut nodes, 4, Some(n5));
	let n3 = add_node(&mut nodes, 3, Some(n4));
	let n2 = add_node(&mut nodes, 2, Some(n3));
	let mut head: Option<usize> = Some(add_node(&mut nodes, 1, Some(n2)));

	let mut prev: Option<usize> = None;
	let mut cursor: Option<usize> = head;
	while let Some(c) = cursor {
		let next = nodes[c].next;
		nodes[c].next = prev;
		prev = Some(c);
		cursor = next;
	}
	head = prev;
	let mut cur = head;
	while let Some(idx) = cur {
		print!("{} -> ", nodes[idx].value);
		cur = nodes[idx].next;
	}
	println!("nil");
}

Complexity

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

Implementation notes

Rust: same three-pointer pattern as the other languages, but each pointer is an Option<usize> index into the Vec<ListNode> arena. The arena avoids the Box<ListNode> ownership-and-take dance the classic Rust 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 raw addresses.

three pointers `prev` starts `None`, `cursor` starts at `head`, `next` is the saved forward link.

rewire The rewire frame flips `cursor.next` from forward (toward `next`) to backward (toward `prev`).