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 -> nil reverses to 5 -> 4 -> 3 -> 2 -> 1 -> nil after five rewire frames.

Basic Implementation

basic.go 
package main

import "fmt"

type ListNode struct {
	Value int
	Next  *ListNode
}

func makeNode(v int, next *ListNode) *ListNode {
	return &ListNode{Value: v, Next: next}
}

func main() {
	n5 := makeNode(5, nil)
	n4 := makeNode(4, n5)
	n3 := makeNode(3, n4)
	n2 := makeNode(2, n3)
	head := makeNode(1, n2)

	var prev *ListNode = nil
	cursor := head
	for cursor != nil {
		next := cursor.Next
		cursor.Next = prev
		prev = cursor
		cursor = next
	}
	head = prev
	for cur := head; cur != nil; cur = cur.Next {
		fmt.Printf("%d -> ", cur.Value)
	}
	fmt.Println("nil")
}

Complexity

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

Implementation notes

  • Go: same three-pointer pattern as the other languages. Each pointer is a *ListNode, and nil represents end-of-list honestly.
  • Reverse in place and reassign head = prev at the end.
  • The replay shows all three pointers each frame and a distinct rewire frame between save and advance, with node(<value>) labels instead of raw addresses.
three pointers `prev` starts `nil`, `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`).