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

Basic Implementation

basic.swift

struct ListNode {
	var value: Int
	var next: Int
}

func addNode(_ nodes: inout [ListNode], _ value: Int, _ next: Int) -> Int {
	let idx = nodes.count
	nodes.append(ListNode(value: value, next: next))
	return idx
}

var nodes: [ListNode] = []
let n5 = addNode(&nodes, 5, -1)
let n4 = addNode(&nodes, 4, n5)
let n3 = addNode(&nodes, 3, n4)
let n2 = addNode(&nodes, 2, n3)
var head = addNode(&nodes, 1, n2)

var prev = -1
var cursor = head
while cursor != -1 {
	let next = nodes[cursor].next
	nodes[cursor].next = prev
	prev = cursor
	cursor = next
}
head = prev
var cur = head
while cur != -1 {
	print("\(nodes[cur].value) -> ", terminator: "")
	cur = nodes[cur].next
}
print("nil")

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

Step 2 - Flip node(1)

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

Step 3 - Reversed prefix reaches 3

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

Step 4 - Done

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

Complexity

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

Implementation notes

Swift: same three-pointer pattern as the other languages, but each pointer is an Int index into the var nodes: [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`).