Solving Reverse a Linked List in Go: Step-by-Step Guide

Introduction to Reversing a Linked List

Reversing a linked list is one of the most classic algorithmic problems every developer encounters, often during technical interviews but also in real-world scenarios involving data structure manipulation. A linked list is a linear data structure where each element (called a node) points to the next one. Reversing it means flipping the direction of these pointers so the last node becomes the first, and the first becomes the last.

In this tutorial, we'll walk through how to implement a singly linked list in Go and reverse it using both an iterative and a recursive approach. We'll also discuss why this problem matters, common pitfalls, and best practices to keep your code clean and efficient.

What Is a Linked List?

A singly linked list is a sequence of nodes where each node contains two parts: a value and a pointer to the next node. The list starts at a "head" node and ends at a node whose next pointer is nil. Unlike arrays, linked lists do not store elements in contiguous memory, which makes insertions and deletions at the head very efficient (O(1)) but random access slow (O(n)).

Defining a Node in Go

In Go, we typically define a linked list node using a struct:

package main

type ListNode struct {
    Val  int
    Next *ListNode
}

The Val field holds the data, and Next is a pointer to the subsequent node. A nil Next value signals the end of the list.

Building a Sample List

Before reversing, let's create a helper function to build a list from a slice of integers:

func buildList(values []int) *ListNode {
    if len(values) == 0 {
        return nil
    }
    head := &ListNode{Val: values[0]}
    current := head
    for i := 1; i < len(values); i++ {
        current.Next = &ListNode{Val: values[i]}
        current = current.Next
    }
    return head
}

We also want a way to print the list so we can verify our reversal:

func printList(head *ListNode) {
    for head != nil {
        fmt.Printf("%d", head.Val)
        if head.Next != nil {
            fmt.Printf(" -> ")
        }
        head = head.Next
    }
    fmt.Println()
}

Why Reversing a Linked List Matters

While reversing a linked list may seem like an academic exercise, it has practical applications:

• Interviews: It tests your understanding of pointers, memory, and edge cases — skills every backend and systems engineer should have.
• Foundation for other algorithms: Problems like palindrome checking, k-group reversal, and merging sorted lists often build on reversal logic.
• Stack-like behavior: Reversing a list can simulate LIFO (last-in, first-out) behavior without allocating a new data structure.
• Memory efficiency: In-place reversal uses O(1) extra space, which is valuable in constrained environments.
• Understanding immutability vs. mutation: It forces you to think carefully about how pointers are reassigned without losing references.

Iterative Approach: Step by Step

The iterative approach is the most common and efficient way to reverse a linked list. The idea is to traverse the list once, and at each step, redirect the current node's Next pointer to the previous node. We need three pointers to do this safely:

• prev: tracks the previous node (starts as nil).
• curr: tracks the current node we're processing.
• next: temporarily stores the next node before we overwrite curr.Next.

The Algorithm

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    curr := head
    for curr != nil {
        next := curr.Next // save the next node
        curr.Next = prev  // reverse the pointer
        prev = curr       // move prev forward
        curr = next       // move curr forward
    }
    return prev
}

After the loop completes, curr is nil and prev points to the new head of the reversed list. Let's trace through an example with the list 1 -> 2 -> 3:

• Initially: prev = nil, curr = 1.
• Iteration 1: next = 2, 1.Next = nil, prev = 1, curr = 2.
• Iteration 2: next = 3, 2.Next = 1, prev = 2, curr = 3.
• Iteration 3: next = nil, 3.Next = 2, prev = 3, curr = nil.
• Loop ends. Return prev, which is the node with value 3.

The final list is 3 -> 2 -> 1 -> nil.

Putting It Together

package main

import "fmt"

type ListNode struct {
    Val  int
    Next *ListNode
}

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    curr := head
    for curr != nil {
        next := curr.Next
        curr.Next = prev
        prev = curr
        curr = next
    }
    return prev
}

func buildList(values []int) *ListNode {
    if len(values) == 0 {
        return nil
    }
    head := &ListNode{Val: values[0]}
    current := head
    for i := 1; i < len(values); i++ {
        current.Next = &ListNode{Val: values[i]}
        current = current.Next
    }
    return head
}

func printList(head *ListNode) {
    for head != nil {
        fmt.Printf("%d", head.Val)
        if head.Next != nil {
            fmt.Printf(" -> ")
        }
        head = head.Next
    }
    fmt.Println()
}

func main() {
    list := buildList([]int{1, 2, 3, 4, 5})
    fmt.Print("Original: ")
    printList(list)

    reversed := reverseList(list)
    fmt.Print("Reversed: ")
    printList(reversed)
}

Running this program produces:

Original: 1 -> 2 -> 3 -> 4 -> 5
Reversed: 5 -> 4 -> 3 -> 2 -> 1

Recursive Approach

The recursive solution is more elegant but uses O(n) stack space due to the call stack. The idea is to recursively reverse the rest of the list, then make the node after the current one point back to the current node.

The Recursive Algorithm

func reverseListRecursive(head *ListNode) *ListNode {
    // Base case: empty list or single node
    if head == nil || head.Next == nil {
        return head
    }
    // Reverse the rest of the list
    newHead := reverseListRecursive(head.Next)
    // Make the next node point back to current node
    head.Next.Next = head
    // Break the original forward link
    head.Next = nil
    return newHead
}

Here's how it works conceptually with the list 1 -> 2 -> 3:

• Call reverseListRecursive(1), which calls reverseListRecursive(2), which calls reverseListRecursive(3).
• reverseListRecursive(3) returns 3 because 3.Next is nil (base case).
• Back in reverseListRecursive(2): 2.Next.Next = 2 means 3.Next = 2, then 2.Next = nil. Returns 3.
• Back in reverseListRecursive(1): 1.Next.Next = 1 means 2.Next = 1, then 1.Next = nil. Returns 3.
• Final list: 3 -> 2 -> 1 -> nil.

The recursive version is concise and demonstrates functional thinking, but be cautious with very long lists because Go's default stack size could lead to a stack overflow.

Handling Edge Cases

A robust implementation must handle several edge cases gracefully:

• Empty list (nil head): Both approaches return nil immediately, which is correct.
• Single-node list: The list is already reversed; both approaches return the same node.
• Two-node list: The iterative approach swaps the pointers in one iteration; the recursive approach handles it in one recursive call.
• Cyclic lists: Neither approach handles cycles. If a cycle exists, the iterative loop will never terminate. Always ensure your input list is acyclic.

Best Practices

When implementing linked list operations in Go, keep these best practices in mind:

• Prefer the iterative approach in production: It uses O(1) space and avoids stack overflow risks on large lists.
• Use clear variable names: prev, curr, and next are widely understood and make the code self-documenting.
• Write tests: Cover empty lists, single-node lists, even-length lists, and odd-length lists to ensure correctness.
• Avoid modifying the list unintentionally: Remember that reversal mutates the original list. If the caller needs the original, document this behavior or return a new list.
• Watch out for nil dereferences: Always check for nil before accessing .Next or .Val.
• Consider generics: In Go 1.18+, you can use type parameters to create a linked list that works with any type, not just integers.

Example Test with Go's Testing Package

package main

import "testing"

func TestReverseList(t *testing.T) {
    tests := []struct {
        name    string
        input   []int
        expected []int
    }{
        {"empty", []int{}, []int{}},
        {"single", []int{1}, []int{1}},
        {"two nodes", []int{1, 2}, []int{2, 1}},
        {"multiple", []int{1, 2, 3, 4, 5}, []int{5, 4, 3, 2, 1}},
    }

    for _, tt := range tests {
        t.Run(tt.name, func(t *testing.T) {
            head := buildList(tt.input)
            reversed := reverseList(head)
            // Convert reversed list back to slice and compare
            result := []int{}
            for reversed != nil {
                result = append(result, reversed.Val)
                reversed = reversed.Next
            }
            if len(result) != len(tt.expected) {
                t.Fatalf("expected %v, got %v", tt.expected, result)
            }
            for i := range result {
                if result[i] != tt.expected[i] {
                    t.Fatalf("expected %v, got %v", tt.expected, result)
                }
            }
        })
    }
}

Conclusion

Reversing a linked list is a fundamental exercise that sharpens your understanding of pointers, memory, and algorithmic thinking. In Go, the iterative approach is straightforward, efficient, and production-ready, while the recursive approach offers a clean, elegant alternative for smaller lists. By mastering both techniques, handling edge cases, and following best practices like thorough testing and clear naming, you'll be well-equipped to tackle not only this problem but also the many linked list variations that build upon it. Whether you're preparing for an interview or writing production code, the discipline of carefully managing pointers will serve you across countless data structure challenges.