如何使用golang語言來實現鍊錶求和的演算法

鍊錶求和是一道常見的演算法問題，它的基本思路是將兩個鍊錶中的數位相加，得出一個新的鍊錶表示它們的和，這個和可能涉及到在進位的情況下的數位增加。

本文將介紹如何使用golang語言來實現鍊錶求和的演算法。

首先，我們需要定義一個鍊錶節點的結構體，它包含兩個欄位：val表示節點的值，next表示指向下一個節點的指標。

type ListNode struct {
    Val  int
    Next *ListNode
}

接下來，我們可以定義一個函數AddTwoNumbers，它接收兩個鍊錶l1和l2，並傳回它們的和所構成的新鍊錶。

func AddTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    carry := 0  // 进位值
    dummy := &ListNode{Val: 0, Next: nil}
    curr := dummy  // 当前节点

    for l1 != nil || l2 != nil {
        // 如果两个链表长度不相等，在较短的链表上添加一个0节点，使两个链表长度相等
        if l1 == nil {
            l1 = &ListNode{Val: 0, Next: nil}
        }
        if l2 == nil {
            l2 = &ListNode{Val: 0, Next: nil}
        }

        sum := l1.Val + l2.Val + carry
        carry = sum / 10  // 更新进位值
        curr.Next = &ListNode{Val: sum % 10, Next: nil}
        curr = curr.Next

        l1 = l1.Next
        l2 = l2.Next
    }

    // 最后如果还有进位，添加一个进位节点
    if carry > 0 {
        curr.Next = &ListNode{Val: carry, Next: nil}
    }

    return dummy.Next
}

在這個函數中，我們用carry變數來表示進位值，初始值為0。我們定義一個啞節點dummy，它指向新鍊錶的頭部，同時定義一個指標curr，用來指向新鍊錶的目前節點，初始值指向啞節點。然後我們使用for循環來遍歷兩個鍊錶，此時我們需要注意，如果兩個鍊錶長度不相等，我們需要在較短的鍊錶上添加一個0節點，使兩個鍊錶長度相等。接下來，我們將鍊錶中同一位置的節點相加，並將進位值和目前節點的值相加，得到一個新的sum值，它的十位數可能進位到下一次相加。因此，我們需要更新carry的值。同時，我們將sum的個位數作為新節點的值，並將curr指標指向這個新建的節點。最後，我們讓curr指標指向新鍊錶的下一個節點，再將l1和l2的指標移向它們的下一個節點。重複這個過程直到兩個鍊錶全部遍歷結束。最後，如果還有進位，新增一個進位節點。最後回到dummy.Next，它代表新鍊錶的頭節點。

接下來我們可以定義測試函數來測試AddTwoNumbers函數。

func TestAddTwoNumbers(t *testing.T) {
    l1 := &ListNode{Val: 2, Next: &ListNode{Val: 4, Next: &ListNode{Val: 3, Next: nil}}}
    l2 := &ListNode{Val: 5, Next: &ListNode{Val: 6, Next: &ListNode{Val: 4, Next: nil}}}
    l3 := AddTwoNumbers(l1, l2)
    if l3.Val != 7 || l3.Next.Val != 0 || l3.Next.Next.Val != 8 || l3.Next.Next.Next != nil {
        t.Errorf("AddTwoNumbers(%v, %v) = %v, want %v", l1, l2, l3, &ListNode{Val: 7, Next: &ListNode{Val: 0, Next: &ListNode{Val: 8, Next: nil}}})
    }
}

在這個測試函數中，我們建立兩個鍊錶l1和l2，它們分別代表342和465。我們呼叫AddTwoNumbers函數，計算它們的和，得到新鍊錶l3，其值應該是708。我們使用if語句對l3的值進行檢查，如果與期望不符，就使用t.Errorf方法記錄錯誤訊息。

將上述程式碼保存在sumLinkedList.go檔案中，執行測試函數，即可得到輸出結果：

$ go test -v
=== RUN   TestAddTwoNumbers
--- PASS: TestAddTwoNumbers (0.00s)
PASS
ok      sumLinkedList  0.360s

透過測試函數，我們可以確認鍊錶求和的演算法實作是正確的。

本文詳細介紹如何使用golang實作鍊錶求和演算法，包含定義鍊錶節點的結構體，以及實作AddTwoNumbers函數的具體步驟。這個演算法是面試中常會遇到的問題，有了自己的實現，可以更好地進行準備，同時也幫助深化對鍊錶和指標的理解。

以上是如何使用golang語言來實現鍊錶求和的演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！