2023JavaScript 程序添加由链接列表表示的两个数字 - 设置 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)。