Dev Skills
Go·Go for coding rounds

Reverse a linked list

Three pointers and one saved link. The question that checks you can move pointers without losing the rest of the list.

Topic 30 of 98 · 5 min to read · 45 min to build
After this topic you can
  • Write an iterative linked-list reversal with O(1) extra space.
  • Predict prev, cur and next at each step of a dry run.
  • Fix the bug of overwriting Next before saving it.

The problem

Given the head of a singly linked list, reverse it and return the new head. 1 → 2 → 3 becomes 3 → 2 → 1.

Brute force first

Walk the list and copy every value into a slice. Walk it again and write the values back from the end of the slice.

O(n) time, O(n) extra space. It also only swaps values, not nodes, which some interviewers will not accept.

The approach

Walk the list once. For each node, save its Next, point it back at the previous node, then step forward. When you fall off the end, prev is the new head. O(n) time, O(1) space.

A recursive version exists, but it uses O(n) stack. Offer it only if asked.

reverse_list.go
package main
import "fmt"
type Node struct {
	Val  int
	Next *Node
}
// reverse flips the links one node at a time and returns the new head.
func reverse(head *Node) *Node {
	var prev *Node
	for cur := head; cur != nil; {
		next := cur.Next // save it before we overwrite the link
		cur.Next = prev
		prev, cur = cur, next
	}
	return prev
}
func build(vals ...int) *Node {
	var head *Node
	for i := len(vals) - 1; i >= 0; i-- {
		head = &Node{Val: vals[i], Next: head}
	}
	return head
}
func show(n *Node) {
	for ; n != nil; n = n.Next {
		fmt.Print(n.Val, " ")
	}
	fmt.Println()
}
func main() {
	show(reverse(build(1, 2, 3, 4, 5))) // 5 4 3 2 1
	show(reverse(build(7)))             // 7
	show(reverse(nil))                  // (empty line)
}

Dry run

1 → 2 → 3. Each row is one loop iteration:

stepnext (saved)cur.Next set toprev aftercur after
start--nil1
12nil12
23123
3nil23nil
endcur is nil, return prev3 → 2 → 1

Go-specific gotchas

  • Save `Next` before you overwrite it. Once cur.Next = prev runs, the rest of the list is gone unless you kept a pointer to it.
  • **A nil *Node is a valid empty list.** var prev *Node starts as nil, and the loop simply does not run for a nil head. No special case needed.
  • Tuple assignment prev, cur = cur, next evaluates the right side first, so the order is safe.
  • Go has container/list, but interviewers want your own Node type for this one.
The short version
  • Three pointers: prev, cur, and the saved next.
  • Save the link before you break it.
  • Return prev, not cur. cur is nil at the end.
Remember: Draw three boxes and the arrows before you write a line. Pointer bugs are drawing bugs.
Build this before moving on
Reverse only the nodes between positions m and n (1-based) and leave the rest in place.
Coding challenge · checked by tests
Write reverseList(head *Node) *Node that reverses a singly linked list by relinking the existing nodes (no new nodes) and returns the new head. Example: 1 → 2 → 3 → 3 → 2 → 1. An empty list stays nil.

Tab indents. Press Esc, then Tab, to leave the editor.

Then try these in your own editor
  1. 1The main task: Reverse only the nodes between positions m and n (1-based) and leave the rest in place.
  2. 2Dry run the loop on a one-node list 5. How many iterations, and what is returned?
  3. 3Check whether a linked list is a palindrome (1 → 2 → 2 → 1 is) in O(n) time and O(1) extra space.
Official documentation
Check yourselfTake the Go for coding rounds test