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

using System;
using System.Collections.Generic;

class ListNode {
	public int Value;
	public int Next;
}

class Program {
	static int AddNode(List<ListNode> nodes, int value, int next) {
		int idx = nodes.Count;
		nodes.Add(new ListNode { Value = value, Next = next });
		return idx;
	}

	static void Main() {
		List<ListNode> nodes = new List<ListNode>();
		int n5 = AddNode(nodes, 5, -1);
		int n4 = AddNode(nodes, 4, n5);
		int n3 = AddNode(nodes, 3, n4);
		int n2 = AddNode(nodes, 2, n3);
		int head = AddNode(nodes, 1, n2);

		int prev = -1;
		int cursor = head;
		while (cursor != -1) {
			int next = nodes[cursor].Next;
			nodes[cursor].Next = prev;
			prev = cursor;
			cursor = next;
		}
		head = prev;
		int cur = head;
		while (cur != -1) {
			Console.Write(nodes[cur].Value + " -> ");
			cur = nodes[cur].Next;
		}
		Console.WriteLine("nil");
	}
}

Complexity

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

Implementation notes

C#: same three-pointer pattern as the other languages, but each pointer is an int index into the List<ListNode> arena (-1 is the sentinel). The arena avoids the ListNode? 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.
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` is the saved forward link.

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