go 中反轉鍊錶

這是新開發者最喜歡提出的問題。如果您上過像樣的資料結構課程，那麼這很簡單。

反轉單一鍊錶。 (這是 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
}

對於反向函數，透過認識到我們需要做的就是維護指向前一個節點的指針，然後將給定節點的「下一個」設定為前一個節點，只需一次傳遞即可完成。

當我們到達末尾時，我們就知道當前節點是清單的新「頭」。

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

我們是否錯過了邊界條件？如果清單現在是雙向鍊錶，會增加哪些複雜度？請在評論中告訴我。

謝謝！

這篇文章以及本系列所有文章的程式碼可以在這裡找到

以上是go 中反轉鍊錶的詳細內容。更多資訊請關注PHP中文網其他相關文章！