Go

Reversing a Linked List in Go: Idiomatic Implementations

LeetCode

— 2 min read

Introduction to Linked Lists in Go

A linked list is a data structure where each element (called a node) contains a value and a pointer to the next node. Unlike arrays, linked lists don't require contiguous memory, making them flexible for dynamic data. In Go, we can represent a linked list using structs and pointers.

Why Reverse a Linked List?

Reversing a linked list is a common interview question and a fundamental operation in many algorithms. For example, reversing a playlist, undoing actions in an editor, or processing data in reverse order all use this concept. Mastering this helps you understand pointers and recursion better.

Basic Structure of a Linked List in Go

Here's how you define a simple linked list in Go:

type Node struct {
    Value int
    Next  *Node
}

Each Node has an integer value and a pointer to the next node. The last node points to nil, marking the end of the list.

Iterative Approach to Reverse a Linked List

The iterative method uses three pointers: prev, current, and next. Here's how it works:

  1. Start with prev as nil and current as the head of the list.
  2. Save the next node of current.
  3. Point current.Next to prev, reversing the link.
  4. Move prev to current and current to next.
  5. Repeat until current is nil.

Here's the code:

func ReverseList(head *Node) *Node {
    var prev *Node
    current := head
    for current != nil {
        next := current.Next
        current.Next = prev
        prev = current
        current = next
    }
    return prev
}

Recursive Approach to Reverse a Linked List

Recursion is another way to reverse a list. The idea is to break the problem into smaller subproblems:

  1. Reverse the rest of the list after the current node.
  2. Point the next node's Next to the current node.
  3. Set the current node's Next to nil.

Here's the recursive implementation:

func ReverseListRecursive(head *Node) *Node {
    if head == nil || head.Next == nil {
        return head
    }
    newHead := ReverseListRecursive(head.Next)
    head.Next.Next = head
    head.Next = nil
    return newHead
}

Comparing Iterative and Recursive Methods

Both methods achieve the same result, but they differ in performance and readability:

  • Iterative: Uses constant space (O(1)) and is generally faster. Easier to understand for beginners.
  • Recursive: Uses stack space (O(n)) due to function calls. More elegant but can cause stack overflow for large lists.

Real-World Use Case: Undo Functionality

Imagine a text editor where each action (like typing or deleting) is stored in a linked list. To undo actions, you reverse the list to process them in reverse order. Here's a simplified example:

type Action struct {
    Command string
    Next    *Action
}

func UndoLastActions(head *Action, steps int) *Action {
    reversed := ReverseList(head)
    for i := 0; i < steps && reversed != nil; i++ {
        fmt.Println("Undoing:", reversed.Command)
        reversed = reversed.Next
    }
    return ReverseList(reversed)
}

Testing Your Implementation

Always test your code with different cases:

  • Empty list (nil).
  • Single-node list.
  • Multi-node list.

Here's a test function:

func TestReverseList(t *testing.T) {
    // Create a list: 1 -> 2 -> 3
    head := &Node{1, &Node{2, &Node{3, nil}}}
    reversed := ReverseList(head)
    // Check if reversed: 3 -> 2 -> 1
    if reversed.Value != 3 || reversed.Next.Value != 2 || reversed.Next.Next.Value != 1 {
        t.Error("Reversed list does not match expected output")
    }
}

Common Pitfalls and How to Avoid Them

When reversing linked lists, watch out for these mistakes:

  • Losing the head pointer: Always save the next node before changing pointers.
  • Infinite loops: Ensure the last node points to nil.
  • Stack overflow: Avoid recursion for very long lists.

Optimizations and Advanced Techniques

For large lists, consider these optimizations:

  • Tail recursion: Some compilers optimize tail-recursive functions to use constant stack space.
  • Parallel processing: Split the list into chunks, reverse each in parallel, and merge.

Conclusion

Reversing a linked list in Go is a great way to practice pointers and recursion. Whether you choose the iterative or recursive method depends on your needs. Use the iterative approach for performance and the recursive one for cleaner code. Test thoroughly and watch out for common pitfalls.

Read more