連結リスト:二つの数を加える

このポストによって、一般的なインタビュー問題の1つであるリンクリストの一連のleetcode問題を始めたいです.今日、我々はAdd Two Numbers Problemを歩いているでしょう.

The problem is, given two non-empty linked lists representing two integers where digits are stored in reverse order, add their digits and return the sum as a linked list.

この問題を解決するために、私たちは初歩的な数学からコラムメソッドを使用するつもりです:私たちが両方のリストの終わりに達するまで、頭からのリスト、数字と数字による数字を通っています.

ここで最初にすることは最後にそれを返さなければならないので新しいリストを作ることです.
指定された関数定義を使用して、デフォルトで0に等しい値を持つ非常に最初のノードを作成します.リストと呼ばれる私たちのリストの頭になります(我々は常に、チェーン全体を返す非常に最初のノードを覚えておく必要があります).実際には、次のノードから始まるリストを返します.
また、現在の反復処理内で動作している現在のノードを指す2番目のカーソルcurrentNodeも必要です.最初に、リストの頭に等しいですが、手動でリストを反復するために使用します.

const addTwoNumbers = (list1, list2) => {
  let list = new ListNode(0); //create a new list
  let currentNode = list; //cursor initialized to list's head
...

  return list.next; //return head's next node (to skip the first 0)
};

次に、2つの追加変数を初期化する必要があります.2つの数字の合計を保持するsumと、2桁の合計が＞10になる場合、次の反復処理を行う桁を持ちます.

...
  let sum = 0;
  let carry = 0;
...

};

次に、2つのリストを繰り返し実行し、その値を合計します.リストのいずれかの端に到達しない限り、ここでwhileループを使用してコードを実行します.また、サイクルの最後までにキャリーリマインダーが残っている場合は、このケースについて考える必要があります.

while (list1 || list2 || sum > 0) { //while list !== null or there's still reminder
...
}

ループ内では、リストが異なる長さを持つ場合、2つのifステートメントがあります.各リストに対する反復の擬似コードは以下の通りです.

現在のリストノードが存在するかどうかを調べます.

合計にその値を追加します.

ポインタカーソルを次のノードに移動します.

while (list1 || list2 || sum > 0) { //while list !== null or there's still reminder
    if (list1) { //check if list !== null in case lists have different sizes
      sum += list1.val;
      list1 = list1.next; //move the pointer
    }
    if (list2) {
      sum += list2.val;
      list2 = list2.next;
    }
...
}

つの反復の終わりまでに、我々は合計値を持ちます.
さて、それが10 = 10かどうかチェックする時間です.それが(例えば、合計が12である)ならば、私たちは第2の桁2だけを取ります、そして、最初の1つは次の反復の上に運ばれます.
この数を2桁に分割するには、数学分割とモジュロ演算を使います.

while (list1 || list2 || sum > 0) {
...
    carry = Math.floor(sum / 10);
    sum = sum % 10;
...
}

今、出力リストに新しいノードを追加し、合計の値を与えることができます.
再び、新しいノードをリストの最後に押すことによって、(1)メモリの割り当て、(2)現在のノードとのリンク、(3)その値の初期化、(4)デフォルトでのNULLへのポインタの設定です.

while (list1 || list2 || sum > 0) {
...
//add a new node to the list, link it with the current node, and give it the value of the sum
    currentNode.next = new ListNode(sum);
...
}

そしてもう一つのことは、次の繰り返しのために追加した新しいノードにcurrentNodeカーソルを進めることです.

while (list1 || list2 || sum > 0) {
...
   //add a new node to the list, link it with the current node, and give it the value of the sum
    currentNode.next = new ListNode(sum);

  //move the cursor to the new node
    currentNode = currentNode.next;
...
}

最後に、我々は次の反復の前にキャリアに合計を初期化する必要があります(我々は、次のラウンドの合計にキャリアを追加するので、合計をリセットします).

while (list1 || list2 || sum > 0) {
...
    sum = carry;
    carry = 0;
}

まとめましょう

const addTwoNumbers = (list1, list2) => {
  let list = new ListNode(0); //create a new list
  let currentNode = list; //cursor initialized to list's head

  let sum = 0;
  let carry = 0;

  while (list1 || list2 || sum > 0) { //while list !== null or there's still reminder
    if (list1) { //check if list !== null in case lists have different sizes
      sum += list1.val;
      list1 = list1.next; //move the pointer
    }
    if (list2) {
      sum += list2.val;
      list2 = list2.next;
    }

    carry = Math.floor(sum / 10);
    sum = sum % 10;

    //add a new node to the list, link it with the current node, and give it the value of the sum
    currentNode.next = new ListNode(sum);

    //move the cursor to the new node
    currentNode = currentNode.next;

    sum = carry;
    carry = 0;
  }

  return list.next; //return head's next node (to skip the first 0)
};

我々は完了です!

複雑さについて

このアプローチの時間複雑さはo(n)である.ここでNはリストを横断しなければならないので、最長リストのノードの最大数である.
スペース複雑さ:O(n)ここで、Nはメモリに新しいリストを作成するので、最長リストのノードの最大数です.
次の二つの問題について議論します.
2つの数を加える
メソッドに2つの数値を追加する
私は、これが助けたことを望みます!あなたが追加のコメントや質問がある場合は私に知らせてください!