Esta es una de las preguntas favoritas para los nuevos desarrolladores. Bastante simple si ha tenido una clase de estructuras de datos decente.

Invertir una única lista enlazada. (Este es Leetcode 206)

Para la implementación, he elegido hacer que la lista enlazada sea de 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
}

Y para la función inversa, se hace con una sola pasada reconociendo que todo lo que necesitamos hacer es mantener un puntero al nodo anterior y luego establecer el "siguiente" de un nodo determinado en el anterior.

Cuando llegamos al final, sabemos que el nodo actual es el nuevo 'encabezado' de la 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
    }
}

¿Hemos omitido una condición de contorno? ¿Qué complicaciones se añaden si la lista ahora es una lista doblemente enlazada? Házmelo saber en los comentarios.

¡Gracias!

El código de esta publicación y todas las publicaciones de esta serie se pueden encontrar aquí