トピックの例
それぞれのデータ構造における足し算、引き算、掛け算、割り算が非常によく調べられます。
| 2つの非負整数を表すために、2つの空でない連結リストが与えられます。それぞれのビットは逆順に格納され、各ノードには1桁しか格納できません。 |
2つの非負整数を表すために、2つの空でない連結リストが与えられます。ビットは逆順に格納され、各ノードには1桁しか格納できません。
一方、2つの数値を足し合わせると、その和を表す新しい連鎖表が返されます。
どちらの数字も0から始まることはないと思ってください。
例
入力： (2> 4 -> 3) + (5 -> 6 -> 4)
アウトプット： 7> 0 -> 8
理由：342 + 465 = 807
アルゴリズム図解
ブリトーノード：ブリトーノードは、最前線に立って、ブリトーのように長いノードがあることを言うことです。多くの場合、最初のノードの子供は、それが牛肉のプルブリトーであるため、一口をかじるために来て、接続をオフにしないプル。まあ、私は本当に気まずい〜を構成することはできません....
センチネル・ノードについてご存じない方は、ぜひご覧ください：
さて、センチネルリンパ節についてはご存知だと思いますが、この質問はセンチネルリンパ節とは関係ありません。 では、質問の正式な分析を始めましょう。
いつものように、チェーンテーブルが＋であると仮定して、まずダイアグラムを描くのがよいでしょう：
足し算は最下位ビットから最上位ビットまで、つまりこの場合は連鎖表の先頭から末尾まで行わなければならないので、連鎖表をトラバースする必要があります。l1とl2を2つのリンクリストの先頭とし、同じビットを加算した結果を格納するtmpの値と、tmpの値を格納する新しいリンクリストを使用します。
覚えておいてください：算数をシミュレートするすべての問題は、丸めを考慮する必要があります。ここでは、1桁目には丸めがないので、10桁目から計算を始めます。また、l1、l2、および新しい連鎖表を次のビットまでたどります。
上記を繰り返すと、十の位と一の位が異なり、丸めが発生していることがわかります。そこで便利なのがtmpです。tmpを使って丸めた値を次の桁に運びます。当然、ここではtmpの値を直接連鎖表に格納することはできず、tmp%10の値を格納します。2つのリンクされたテーブルを巡回し、tmpに丸められた値がなくなるまで、このステップを繰り返します：
あとは新しいリンク・テーブルを返すだけです。問題は、センチネルノードが構築されていないため、この時点で新しいリンクされたテーブルを直接返すのは簡単ではないということです。そのため、全体のプロセスの最初のステップでは、センチネルノードが指す新しいリンクされたテーブルも必要になります。
それを分析した後、コードに直行します：
//go
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
list := &ListNode{0, nil}
//ここでの結果の使用は、後でノードを返す便宜のためであり、それ以外の目的ではない。
result := list
tmp := 0
for l1 != nil || l2 != nil || tmp != 0 {
if l1 != nil {
tmp += l1.Val
l1 = l1.Next
}
if l2 != nil {
tmp += l2.Val
l2 = l2.Next
}
list.Next = &ListNode{tmp % 10, nil}
tmp = tmp / 10
list = list.Next
}
return result.Next
}
実施結果：
私が書いたすべての解答と各問題の完全な図解をeBookにまとめました。クリックしてダウンロード
