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)。