golang 言語を使用してリンクリスト合計アルゴリズムを実装する方法

リンク リストの合計は、一般的なアルゴリズムの問​​題です。その基本的な考え方は、2 つのリンク リストの数字を加算して、その合計を表す新しいリンク リストを取得することです。この合計には桁上げ桁数の増加が含まれる場合があります。

この記事では、golang 言語を使用してリンク リスト合計アルゴリズムを実装する方法を紹介します。

まず、リンク リスト ノードの構造を定義する必要があります。これには 2 つのフィールドが含まれます。val はノードの値を表し、next は次のノードへのポインターを表します。

type ListNode struct {
    Val  int
    Next *ListNode
}

次に、関数 AddTwoNumbers を定義できます。この関数は、2 つのリンク リスト 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
}

この関数では、キャリー変数を使用してキャリー値を表し、初期値は 0 です。新しいリンク リストの先頭を指すダミー ノード dummy と、新しいリンク リストの現在のノードを指すポインター curr を定義します。初期値はダミー ノードを指します。次に、for ループを使用して 2 つのリンク リストを走査します。このとき、2 つのリンク リストの長さが等しくない場合は、短い方のリンク リストに 0 ノードを追加して 2 つのリンク リストを作成する必要があることに注意する必要があります。リストの長さが等しい。次に、リンクされたリストの同じ位置にノードを追加し、現在のノードの値にキャリー値を加算して新しい合計値を取得します。その 10 の位は次の加算でキャリーされる可能性があります。したがって、キャリーの値を更新する必要があります。同時に、合計の 1 桁を新しいノードの値として使用し、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}}})
    }
}

このテスト関数では、それぞれ 342 と 465 を表す 2 つのリンク リスト l1 と l2 を作成します。 AddTwoNumbers 関数を呼び出し、それらの合計を計算し、値が 708 である新しいリンク リスト l3 を取得します。 if ステートメントを使用して l3 の値を確認し、期待どおりでない場合は、t.Errorf メソッドを使用してエラー メッセージを記録します。

上記のコードを sumLinkedList.go ファイルに保存し、テスト関数を実行すると、出力結果が得られます。

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

テスト関数を通じて、リンク リストの合計アルゴリズムは正しいです。

この記事では、リンク リストのノードの構造の定義や、AddTwoNumbers 関数を実装する具体的な手順など、golang を使用してリンク リストの合計アルゴリズムを実装する方法を詳しく紹介します。このアルゴリズムは面接でよく聞かれる質問であり、独自に実装することで準備が整い、リンク リストやポインタについての理解を深めることもできます。

以上がgolang 言語を使用してリンクリスト合計アルゴリズムを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。