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

import scala.collection.mutable.ArrayBuffer

class ListNode(var value: Int, var next: Int)

object Main {
	def addNode(nodes: ArrayBuffer[ListNode], value: Int, next: Int): Int = {
		val idx = nodes.length
		nodes += new ListNode(value, next)
		idx
	}

	def main(args: Array[String]): Unit = {
		val nodes = ArrayBuffer.empty[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(s"${nodes(cur).value} -> ")
			cur = nodes(cur).next
		}
		println("nil")
	}
}

Complexity

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

Implementation notes

Scala: same three-pointer pattern as the other languages, but each pointer is an Int index into the ArrayBuffer[ListNode] arena (-1 is the sentinel). The arena avoids the Option[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`).