golang怎麼實作反轉鍊錶

反轉鍊錶是常見的一個問題，在程式面試中也常被提及。它是一道經典的演算法問題，應用廣泛，可以用於快速反轉鍊錶的順序。本文將介紹使用golang語言實作反轉鍊錶的演算法和步驟。

1. 定義單鍊錶節點

在開始實作反轉鍊錶之前，我們需要先定義一個單鍊錶的節點。一個節點包含兩個非常重要的部分：資料域和指標域。資料域用來儲存節點的值，指標域用來指向下一個節點。

在golang中，我們可以使用struct結構體來定義一個單鍊錶節點。結構體包含兩個屬性：Val，用來表示目前節點的值，Next，用來表示指向下一個節點的指標。

type ListNode struct {

Val  int
Next *ListNode

}

2. #單鍊錶反轉

現在我們已經定義了單鍊錶的節點，下一步是實作反轉鍊錶的演算法。反轉鍊錶的關鍵是遍歷鍊錶並更改每個節點的指標指向。

我們可以從頭開始遍歷鍊錶中的每個節點，並且依序改變它們的「Next」指針，指向前一個節點。這樣就可以實現鍊錶的反轉了。

反轉鍊錶的演算法步驟如下：

（1）定義兩個指標：pre和cur，分別指向第一個節點和第二個節點。 pre為前一個節點，cur為當前節點。

（2）遍歷鍊錶，分別將目前節點的Next指標指向前一個節點pre。

（3）向後移動指針，將pre指向目前節點，cur指向下一個節點。

（4）重複步驟2和3，直到遍歷完整個鍊錶。

實作程式碼如下：

func reverseLinkedList(head ListNode) ListNode {

var pre *ListNode
cur := head
for cur != nil {
    next := cur.Next
    cur.Next = pre
    pre = cur
    cur = next
}
return pre

}

##反轉鍊錶的測試程式碼

為了驗證反轉鍊錶的正確性，我們會寫一些測試程式碼來執行。

func TestReverseLinkedList(t *testing.T) {

head := &ListNode{Val: 1}
node1 := &ListNode{Val: 2}
node2 := &ListNode{Val: 3}
node3 := &ListNode{Val: 4}
node4 := &ListNode{Val: 5}

head.Next = node1
node1.Next = node2
node2.Next = node3
node3.Next = node4

newHead := reverseLinkedList(head)

assert.Equal(t, newHead.Val, 5)
assert.Equal(t, newHead.Next.Val, 4)
assert.Equal(t, newHead.Next.Next.Val, 3)
assert.Equal(t, newHead.Next.Next.Next.Val, 2)
assert.Equal(t, newHead.Next.Next.Next.Next.Val, 1)

}

反轉部分鍊錶
4. ##除了反轉整個鍊錶之外，我們還可以反轉鍊錶中的一部分。例如，反轉鍊錶中第m個節點到第n個節點的部分。我們只需要在反轉整個鍊錶的基礎上稍作修改即可。

我們可以先遍歷到第m-1個節點，pre指標指向該節點，cur指向第m個節點。然後，我們執行反轉鍊錶的步驟，直到反轉到第n個節點為止。

實作程式碼如下：

func reverseBetween(head

ListNode, m int, n int)

ListNode {

dummy := &ListNode{0, head}
pre := dummy

for i := 1; i < m; i++ {
    pre = pre.Next
}

cur := pre.Next
for i := m; i < n; i++ {
    next := cur.Next
    cur.Next = next.Next
    next.Next = pre.Next
    pre.Next = next
}

return dummy.Next

}

#反轉部分鍊錶的測試程式碼

5. 為了驗證反轉部分鍊錶的正確性，我們寫一些測試程式碼進行驗證。

func TestReverseBetween(t *testing.T) {

head := &ListNode{Val: 1}
node1 := &ListNode{Val: 2}
node2 := &ListNode{Val: 3}
node3 := &ListNode{Val: 4}
node4 := &ListNode{Val: 5}

head.Next = node1
node1.Next = node2
node2.Next = node3
node3.Next = node4

newHead := reverseBetween(head, 2, 4)

assert.Equal(t, newHead.Val, 1)
assert.Equal(t, newHead.Next.Val, 4)
assert.Equal(t, newHead.Next.Next.Val, 3)
assert.Equal(t, newHead.Next.Next.Next.Val, 2)
assert.Equal(t, newHead.Next.Next.Next.Next.Val, 5)

}

總結

6. 在本文中，我們使用golang實現了反轉鍊錶演算法，包括反轉整個鍊錶和反轉部分鍊錶。反轉鍊錶是一道常見的面試題，同時也是解決鍊錶相關問題的基礎演算法。如果您對鍊錶演算法感興趣，建議您深入學習其他鍊錶相關演算法，例如快慢指針，環形鍊錶，刪除節點等等。

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