So verwenden Sie die Golang-Sprache, um den Summierungsalgorithmus für verknüpfte Listen zu implementieren

Das Summieren verknüpfter Listen ist ein häufiges Algorithmusproblem. Die Grundidee besteht darin, die Ziffern in zwei verknüpften Listen zu addieren, um eine neue verknüpfte Liste zu erhalten, die deren Summe darstellt.

In diesem Artikel wird erläutert, wie Sie mithilfe der Golang-Sprache den Summierungsalgorithmus für verknüpfte Listen implementieren.

Zuerst müssen wir eine Struktur verknüpfter Listenknoten definieren, die zwei Felder enthält: val stellt den Wert des Knotens dar und next stellt den Zeiger auf den nächsten Knoten dar.

type ListNode struct {
    Val  int
    Next *ListNode
}

Als nächstes können wir eine Funktion AddTwoNumbers definieren, die zwei verknüpfte Listen l1 und l2 empfängt und eine neue verknüpfte Liste zurückgibt, die aus ihrer Summe besteht.

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
}

In dieser Funktion verwenden wir die Übertragsvariable, um den Übertragswert darzustellen, und der Anfangswert ist 0. Wir definieren einen Dummy-Knoten, der auf den Kopf der neuen verknüpften Liste zeigt, und einen Zeiger curr, der auf den aktuellen Knoten der neuen verknüpften Liste zeigt, wobei der Anfangswert auf den Dummy-Knoten zeigt. Dann verwenden wir eine for-Schleife, um die beiden verknüpften Listen zu durchlaufen. Zu diesem Zeitpunkt müssen wir beachten, dass wir der kürzeren verknüpften Liste einen 0-Knoten hinzufügen müssen, um die beiden zu erstellen verknüpfte Listen gleicher Länge. Als nächstes fügen wir die Knoten an derselben Position in der verknüpften Liste hinzu und addieren den Übertragswert zum Wert des aktuellen Knotens, um einen neuen Summenwert zu erhalten, dessen Zehnerstelle bei der nächsten Addition übernommen werden kann. Daher müssen wir den Wert von Carry aktualisieren. Gleichzeitig verwenden wir die einzelne Ziffer der Summe als Wert des neuen Knotens und zeigen den aktuellen Zeiger auf diesen neu erstellten Knoten. Schließlich lassen wir den aktuellen Zeiger auf den nächsten Knoten der neuen verknüpften Liste zeigen und bewegen dann die Zeiger von l1 und l2 auf ihre nächsten Knoten. Wiederholen Sie diesen Vorgang, bis beide verknüpften Listen durchlaufen wurden. Wenn schließlich ein Übertrag vorhanden ist, fügen Sie einen Übertragsknoten hinzu. Schließlich wird dummy.Next zurückgegeben, das den Kopfknoten der neuen verknüpften Liste darstellt.

Als nächstes können wir eine Testfunktion definieren, um die AddTwoNumbers-Funktion zu testen.

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

In dieser Testfunktion erstellen wir zwei verknüpfte Listen l1 und l2, die 342 bzw. 465 darstellen. Wir rufen die Funktion AddTwoNumbers auf, berechnen ihre Summe und erhalten die neue verknüpfte Liste l3, deren Wert 708 sein sollte. Wir verwenden die if-Anweisung, um den Wert von l3 zu überprüfen. Wenn er den Erwartungen nicht entspricht, verwenden wir die t.Errorf-Methode, um die Fehlermeldung aufzuzeichnen.

Speichern Sie den obigen Code in der Datei sumLinkedList.go, führen Sie die Testfunktion aus und Sie erhalten das Ausgabeergebnis:

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

Durch die Testfunktion können wir bestätigen, dass die Implementierung des Summierungsalgorithmus für verknüpfte Listen korrekt ist.

In diesem Artikel wird detailliert beschrieben, wie Golang zum Implementieren des Summationsalgorithmus für verknüpfte Listen verwendet wird, einschließlich der Definition der Struktur verknüpfter Listenknoten und der spezifischen Schritte zum Implementieren der AddTwoNumbers-Funktion. Dieser Algorithmus wird häufig in Interviews gestellt. Mit seiner eigenen Implementierung können Sie sich besser vorbereiten und Ihr Verständnis für verknüpfte Listen und Zeiger vertiefen.

Das obige ist der detaillierte Inhalt vonSo verwenden Sie die Golang-Sprache, um den Summierungsalgorithmus für verknüpfte Listen zu implementieren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!