Это любимый вопрос, который задают начинающим разработчикам. Довольно просто, если у вас есть приличный класс по структурам данных.

Реверс одного связанного списка. (Это Leetcode 206)

Для реализации я решил сделать связанный список общим типом.

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
}

А для обратной функции это делается за один проход, поскольку все, что нам нужно сделать, это сохранить указатель на предыдущий узел, а затем установить значение «next» данного узла на предыдущий.

Когда мы доходим до конца, мы знаем, что текущий узел является новым «головой» списка.

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

Пропустили ли мы граничное условие? Какие сложности добавляются, если список теперь является двусвязным? Дай мне знать в комментариях.

Спасибо!

Код этого поста и всех постов этой серии можно найти здесь