JavaScript 程式會新增由連結清單表示的兩個數字 - 設定 1

將兩個數字相加是一項簡單的任務，但如果數字以鍊錶的形式給出，則可能會很棘手。鍊錶的每個節點從第一個節點到最後一個節點以連續的方式包含它所代表的數字的數字。我們將得到兩個代表兩個不同數字的鍊錶，我們必須將它們相加並以鍊錶的形式傳回第三個數字。

輸入

1 -> 2 -> 3 -> null
3 -> 2 -> 4 -> null

輸出

4 -> 4 -> 7 -> null

說明：給定第一個數是123，第二個數是324，它們的和是447，我們以鍊錶的形式回傳。

轉換為數字方法

在這種方法中，首先，我們將給定的數字從鍊錶表示形式轉換為整數形式，然後應用加法運算。之後，我們將結果轉換為鍊錶，最後返回列印答案鍊錶中存在的資料。

範例

// class to create the structure of the nodes 
class Node{
   constructor(data){
      this.value = data;
      this.next = null;
   }
}

// function to print the linked list
function print(head){
   var temp = head;
   var ans = ""
   while(temp.next != null){
      ans += temp.value;
      ans += " -> "
      temp = temp.next
   }
   ans += temp.value
   ans += " -> null"
    
   console.log(ans)
}

// function to add data in linked list 
function add(data, head, tail){
   return tail.next = new Node(data);
}

// function to convert linked list to number 
function LL_to_int(head){
   var temp = "";
   var cur = head;
   while(cur != null){
      temp += cur.value.toString();
      cur = cur.next;
   }
   return parseInt(temp);
}

// function to convert number to linked list
function num_to_LL(num){
   var str = num.toString();
   var head = new Node(str[0]-'0');
   var tail = head;
   for(var i = 1; i<str.length; i++){
      tail = add(str[i]-'0',head, tail);
   }
   
   // final number is 
   console.log("The final answer is: ")
   print(head);
}

// defining first number
var num1  = new Node(1)
var tail  = num1
tail = add(2,num1, tail)
tail = add(3,num1, tail)
console.log("The given first number is: ")
print(num1)

// defining second number
var num2 = new Node(3)
tail  = num2
tail = add(2,num2, tail)
tail = add(4,num2, tail)
console.log("The given second number is: ")
print(num2)

// converting both the linked list into the actual values
int_num1 = LL_to_int(num1)
int_num2 = LL_to_int(num2)
var ans = int_num1 + int_num2;

// converting number to the linked list 
num_to_LL(ans);

輸出

The given first number is: 
1 -> 2 -> 3 -> null
The given second number is: 
3 -> 2 -> 4 -> null
The final answer is: 
4 -> 4 -> 7 -> null

時間與空間複雜度

上述程式碼的時間複雜度為(M N)，其中M和N是給定鍊錶的大小。

上面程式碼的空間複雜度是O(N)，因為我們建立了一個新的鍊錶。

另一種方法

在這種方法中，我們將透過從末尾遍歷到第一個節點來新增鍊錶元素，直到第一個鍊錶值變為零。當once變為零時，將其值為零並移動，直到它們都變為零。

範例

// class to create the structure of the nodes 
class Node{
   constructor(data){
      this.value = data;
      this.next = null;
   }
}

// function to print the linked list
function print(head){
   var temp = head;
   var ans = ""
   while(temp.next != null){
      ans += temp.value;
      ans += " -> "
      temp = temp.next
   }
   ans += temp.value
   ans += " -> null"
   console.log(ans)
}

// function to add data in linked list 
function add(data, head, tail){
   return tail.next = new Node(data);
}

// function to convert string to linked list
function num_to_LL(str){
   var head = new Node(str[str.length-1]-'0');
   var tail = head;
   for(var i = str.length-2; i>=0; i--){
      tail = add(str[i]-'0',head, tail);
   }
   
   // final number is 
   console.log("The final answer is: ")
   print(head);
}

// function to add values of the linked lists
function addLL(ll1, ll2){
   var str = "";
   var carry = 0;
   while((ll1 != null) || (ll2 != null)){
      if(ll1 == null){
         carry += ll2.value;
         ll2 = ll2.next;
      }  else if(ll2 == null){
         carry += ll1.value;
         ll1 = ll1.next;
      }  else {
         carry += ll1.value + ll2.value;
         ll2 = ll2.next;
         ll1 = ll1.next;
      }
      str += (carry%10).toString();
      carry /= 10;
      carry = Math.floor(carry);
   }
   if(carry != 0){
      str += (carry%10).toString();
   }
   
   // calling function to print the answer
   num_to_LL(str);
}

// defining first number in reverse manner 
var num1  = new Node(3)
var tail  = num1
tail = add(2,num1, tail)
tail = add(1,num1, tail)
console.log("The given first number in reverse manner is: ")
print(num1)

// defining second number
var num2 = new Node(4)
tail  = num2
tail = add(2,num2, tail)
tail = add(3,num2, tail)
console.log("The given second number in reverse manner is: ")
print(num2)

// calling to the add function 
addLL(num1,num2);

輸出

The given first number is: 
1 -> 2 -> 3 -> null
The given second number is: 
3 -> 2 -> 4 -> null
The final answer is: 
4 -> 4 -> 7 -> null

結論

在本教程中，我們實作了 JavaScript 程式碼來將兩個以鍊錶形式給出的數字相加，並以鍊錶形式傳回結果。我們實作了兩種方法，時間和空間複雜度均為 O(N)。

以上是JavaScript 程式會新增由連結清單表示的兩個數字 - 設定 1的詳細內容。更多資訊請關注PHP中文網其他相關文章！