DEV Community

J Fowler
J Fowler

Posted on

Reverse a linked list in go

This is a favorite question to give to new developers. Pretty simple if you have had a decent data structures class.

Reverse a single linked list. (This is Leetcode 206)

For the implementation, I have chosen to make the linked list a generic type.

type Node[T any] struct {
    Data T
    Next *Node[T]
}

type LinkedList[T any] struct {
    Head *Node[T]
}

func (ll *LinkedList[T]) Append(data T) {
    newNode := &Node[T]{Data: data, Next: nil}

    if ll.Head == nil {
        ll.Head = newNode
        return
    }

    current := ll.Head
    for current.Next != nil {
        current = current.Next
    }
    current.Next = newNode
}
Enter fullscreen mode Exit fullscreen mode

And for the reverse function, it's done with a single pass by recognizing that all we need to do is maintain a pointer to the previous node, then set a given node's 'next' to the previous.

When we reach the end, then we know the current node is the new 'head' of the list.

func (ll *LinkedList[T]) ReverseLinkedList() {
    var prev *Node[T] = nil
    var ptr *Node[T] = ll.Head
    for ptr != nil {
        var next *Node[T] = ptr.Next
        ptr.Next = prev
        prev = ptr
        if next == nil {
            ll.Head = ptr
        }
        ptr = next
    }
}
Enter fullscreen mode Exit fullscreen mode

Have we missed a boundary condition? What complications are added if the list is now a doubly linked list? Let me know in the comments.

Thanks!

The code for this post and all posts in this series can be found here

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

Top comments (0)

The Most Contextual AI Development Assistant

Pieces.app image

Our centralized storage agent works on-device, unifying various developer tools to proactively capture and enrich useful materials, streamline collaboration, and solve complex problems through a contextual understanding of your unique workflow.

👥 Ideal for solo developers, teams, and cross-company projects

Learn more