インタビュアー: 「最後にアルゴリズムを書いてください。単一のリンクリストを使用して加算を実行してみましょう...」

[[286163]]

質問: 空でない 2 つのリンク リストが与えられた場合、2 つの負でない整数を表します。それらの間では、それぞれの数字が逆の順序で格納され、各ノードには 1 つの数字しか格納できません。 2 つのリンク リストを加算し、その合計を表す新しいリンク リストを返します。

例: 342 + 465 = 807

2 つの数値を加算する問題は、最も単純な数学的加算演算を伴いますが、リンク リストに基づいているため、リンク リストの処理に難しさがあります。

加算演算では、各ビットを加算するだけでなく、桁上げの状況も考慮する必要があります。この問題では、連結リストの各ノードに数字が格納され、自然数に基づいて逆順に格納されます。つまり、チェーンの先頭から末尾まで、低い値から高い値への順序が維持されます。つまり、桁上げの方向は単一の連結リストの方向と一致します。

単方向リンクリストの特性上、先行ノードが存在せず、戻ることはできません。この問題のシナリオでは、チェーンの先頭 (低い位置) からチェーンの終わり (高い位置) まで処理する while ループが 1 つだけ必要で、問題を解決できます。ただし、繰り上がり状況の処理には注意が必要です。計算後、各ノードは余りを 10 で割って保存する必要があります。余りは、計算に参加するために次のノードに繰り上がる必要があり、これは単一のリンク リストの処理の考え方と一致しています。

次に、いくつかの変数、各ビット操作後のキャリーを記録するキャリー、および 2 つのリンク リストの加算操作後のリンク リスト ノードを記録するダミー ノードが必要になります。

最長のリンクリストの最後のノードを処理するときは、キャリーに対して追加の処理を実行する必要があります。キャリーが 0 でない場合は、キャリーがより高い位置まで続くことを意味し、キャリーを格納するための新しいノードを作成する必要があります。

ここでの説明は明確です。コードに直接進みましょう。

パブリックリストノード addTwoNumbers(リストノード l1、リストノード l2) {
  // 計算結果を格納するダミーノード
  ListNode ダミー = 新しい ListNode(0);
  リストノード p = l1、q = l2、curr = ダミー;
  // 繰り上がりのデフォルトは 0 です
整数キャリー = 0;
  // ループに入り、p と q のリンクリストポインタが両方とも末尾に到達したら終了します
  (p != null || q != null ) の場合 {
 int x = (p != null ) ? p.val : 0;
 int y = (q != null ) ? q.val : 0;
    // キャリーが操作に参加する
整数 合計= 繰り上がり + x + y;
    // キャリーを計算する
    繰り上がり =合計/ 10;
    //計算された数字の値を格納するための新しいノードを構築します
    curr.next = 新しいListNode(合計% 10 );
    curr = curr.next ;
    (p != null )の場合
      p = p.next ;
    （q != null ）の場合
      q = q.next ;
  }
  // 数値の最上位桁の末尾の繰り上がりを処理する
  （キャリー＞0）の場合{
    curr.next = 新しいListNode(carry);
  }
 dummy.nextを返します。
 }

ここで、p と q は、ループの基礎となる 2 つのリンク リスト l1 と l2 のノードをそれぞれ格納するために使用されます。ループを終了する条件は、両方のリンク リストが末尾に到達していることです。

各ループでは、各ノードの値が処理され、繰り上がり値が加算されます。演算後、残りの値は新しいノードに格納され、新しい繰り上がり値は保存用にキャリーに格納されます。

最後に、両方のリンク リストが処理された後、最上位ビットを繰り上げる必要があるかどうか (繰り上げ > 0) を判断する必要があることに注意してください。必要に応じて、繰り上がり値を格納するための新しいリンク リスト ノードを作成します。

リンク リストを使用して加算演算を実行するこの問題の説明はこれで終わりですが、これにはいくつかのバリエーションもあります。

リンク リストが数字をビットごとに逆順で格納しない場合はどうなるでしょうか。順順で格納した場合はどうなるでしょうか。

例えば：

1 → 2 → 3

+ 3 → 2 → 1

=> 123 + 321 = ?

[この記事は51CTOコラムニスト「張楊」によるオリジナル記事です。転載の許可を得るにはWeChat公式アカウントを通じて著者に連絡してください]

この著者の他の記事を読むにはここをクリックしてください