How to Efficiently Reverse a Linked List in Go

Problem Statement

You’re given the head of a linked list. The goal is to write a function that takes that first node and (whether iteratively or recursively) reverse the linked list. For example, if you had the linked list 2 -> 5 -> 0 -> 3 -> 8, you should be able to run some program to transform that into 8 -> 3 -> 0 -> 5 -> 2. In this post, we are going to use the recursive approach.

Definition

Let’s first define the type for a node in the linked list…

 type ListNode struct {
      Val int
      Next *ListNode
 }

Swap Function

Let’s also define a helper function for swapping nodes.

func swapNodes(node1, node2 *ListNode) *ListNode {
    node1.Next = nil // This line prevents circularity
    temp := node1
    node1 = node2
    node1.Next = temp
    return node1
}

Recursive Function with Defer

Then we need the actual recursive function. So what’s happening here? As it traverses the linked list, it pushes swap actions onto the stack using the defer statement. In other words, it traverses to the end of the linked list before making swaps in LIFO order. Our base case here is simply to return the node, which points to the head of the linked list.

func reverseListFunc(node *ListNode) *ListNode {
    if (node.Next != nil) {
        defer swapNodes(node, node.Next)
        return reverseListFunc(node.Next)
    }
    return node
}

Wrapper

Ok, so all that’s left is a trivial wrapper around this recursive function! The wrapper is there to make sure that we don’t try to reverse an empty list. And there we go, a concise and O(N) reversal of the linked list (with some sprinkles on top).

func reverseList(head *ListNode) *ListNode {
    if (head == nil) {
        return nil
    }
    return reverseListFunc(head)
}