Reverse a linked list in go



This content originally appeared on DEV Community and was authored by Johns Code

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.

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
}

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
    }
}

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


This content originally appeared on DEV Community and was authored by Johns Code