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

Canonical input 1 -> 2 -> 3 -> 4 -> 5 -> null reverses to 5 -> 4 -> 3 -> 2 -> 1 -> null after five rewire frames.

Basic Implementation

basic.R 
add_node <- function(nodes, value, next_idx) {
	idx <- length(nodes) + 1
	nodes[[idx]] <- list(value = value, next_idx = next_idx)
	list(nodes = nodes, idx = idx)
}

nodes <- list()
r <- add_node(nodes, 5, -1); nodes <- r$nodes; n5 <- r$idx
r <- add_node(nodes, 4, n5); nodes <- r$nodes; n4 <- r$idx
r <- add_node(nodes, 3, n4); nodes <- r$nodes; n3 <- r$idx
r <- add_node(nodes, 2, n3); nodes <- r$nodes; n2 <- r$idx
r <- add_node(nodes, 1, n2); nodes <- r$nodes; head <- r$idx

prev <- -1
cursor <- head
while (cursor != -1) {
	next_idx <- nodes[[cursor]]$next_idx
	nodes[[cursor]]$next_idx <- prev
	prev <- cursor
	cursor <- next_idx
}
head <- prev
cur <- head
while (cur != -1) {
	cat(nodes[[cur]]$value, " -> ", sep = "")
	cur <- nodes[[cur]]$next_idx
}
cat("null\n", sep = "")

Complexity

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

Implementation notes

  • R: same three-pointer pattern as the other languages, but each pointer is an integer index into the nodes list arena (-1 is the sentinel). The arena avoids R's copy-on-modify semantics fighting with the classic reference idiom 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.
  • add_node receives the arena as a parameter and returns the new arena plus the appended index because R copies list arguments by value; the caller threads the updated arena through each r <- add_node(...); nodes <- r$nodes; nX <- r$idx line. The lesson notes this is a side-effect-free way to model the spec's "mutate the shared arena" idea.
  • 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_idx` is the saved forward link.
rewire The rewire frame flips `cursor.next_idx` from forward (toward `next`) to backward (toward `prev`).