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
}

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