Linked Structures

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.kt 
class ListNode(var value: Int, var next: Int)

fun addNode(nodes: MutableList<ListNode>, value: Int, next: Int): Int {
	val idx = nodes.size
	nodes.add(ListNode(value, next))
	return idx
}

fun main() {
	val nodes = mutableListOf<ListNode>()
	val n5 = addNode(nodes, 5, -1)
	val n4 = addNode(nodes, 4, n5)
	val n3 = addNode(nodes, 3, n4)
	val n2 = addNode(nodes, 2, n3)
	var head = addNode(nodes, 1, n2)

	var prev = -1
	var cursor = head
	while (cursor != -1) {
		val next = nodes[cursor].next
		nodes[cursor].next = prev
		prev = cursor
		cursor = next
	}
	head = prev
	var cur = head
	while (cur != -1) {
		print("${nodes[cur].value} -> ")
		cur = nodes[cur].next
	}
	println("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).

Initial 1 -> 2 -> 3 -> 4 -> 5 chain with prev, cursor, and nxt named.prevcursornxtnullnode(1)node(2)node(3)node(4)node(5)

Step 2 - Flip node(1)

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

After the first flip, prev points at node(1) and cursor advances to node(2).prevcursornode(1)nullnode(2)node(3)node(4)node(5)

Step 3 - Reversed prefix reaches 3

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

Middle of the reverse: prefix 3 -> 2 -> 1, suffix 4 -> 5.prevcursornode(3)node(2)node(1)nullnode(4)node(5)

Step 4 - Done

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

Final reversed list.headnode(5)node(4)node(3)node(2)node(1)null

Complexity

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

Implementation notes

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