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
}

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

The above is the detailed content of Reverse a linked list in go. For more information, please follow other related articles on the PHP Chinese website!