資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究用連結串列表示的兩個數字相加 - 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)，因為我們建立了一個新的連結串列。
另一種方法
在這種方法中，我們將透過從末尾到第一個節點遍歷它們來新增連結串列元素，直到其中一個連結串列的值變為零。當其中一個變為零時，將其值視為零，並繼續移動，直到兩者都變為零。
示例
// 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)。
更新於： 2023年5月4日
181 次檢視
廣告