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

[[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を返します。
 }