Esta é uma pergunta favorita para novos desenvolvedores. Muito simples se você tiver uma classe de estruturas de dados decente.

Inverter uma única lista vinculada. (Este é o Leetcode 206)

Para a implementação, optei por tornar a lista vinculada um tipo genérico.

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
}

E para a função reversa, isso é feito com uma única passagem, reconhecendo que tudo o que precisamos fazer é manter um ponteiro para o nó anterior e, em seguida, definir o 'próximo' de um determinado nó para o anterior.

Quando chegarmos ao final, saberemos que o nó atual é o novo 'cabeçalho' da lista.

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

Perdemos uma condição de limite? Que complicações serão adicionadas se a lista for agora uma lista duplamente vinculada? Deixe-me saber nos comentários.

Obrigado!

O código desta postagem e de todas as postagens desta série podem ser encontrados aqui