Program JavaScript menambah dua nombor yang diwakili oleh senarai terpaut - Persediaan 1

Menambah dua nombor adalah tugas yang mudah tetapi boleh menjadi rumit jika nombor itu diberikan dalam bentuk senarai terpaut. Setiap nod senarai terpaut mengandungi nombor nombor yang diwakilinya secara berterusan dari nod pertama hingga nod terakhir. Kami akan mendapat dua senarai terpaut yang mewakili dua nombor berbeza dan kami perlu menambahnya dan mengembalikan nombor ketiga dalam bentuk senarai terpaut.

Masuk

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

Output

4 -> 4 -> 7 -> null

Penjelasan: Memandangkan nombor pertama ialah 123, nombor kedua ialah 324, dan jumlahnya ialah 447, kami mengembalikannya dalam bentuk senarai terpaut.

Tukar kepada kaedah digital

Dalam kaedah ini, mula-mula, kami menukar nombor yang diberikan daripada perwakilan senarai terpaut kepada bentuk integer dan kemudian menggunakan operasi tambah. Selepas itu, kami menukar hasilnya kepada senarai terpaut dan akhirnya kembali untuk mencetak data yang ada dalam senarai terpaut jawapan.

Contoh

// 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);

Output

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

Kerumitan masa dan ruang

Kerumitan masa kod di atas ialah (M+N), dengan M dan N ialah saiz senarai terpaut yang diberikan.

Kerumitan ruang kod di atas ialah O(N) kerana kami membuat senarai terpaut baharu.

Cara lain

Dalam kaedah ini, kami akan menambah elemen senarai terpaut dengan merentasi dari hujung ke nod pertama sehingga nilai senarai terpaut pertama menjadi sifar. Apabila sekali menjadi sifar, tetapkan nilainya kepada sifar dan gerakkan sehingga kedua-duanya menjadi sifar.

Contoh

// 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);

Output

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

Kesimpulan

Dalam tutorial ini, kami melaksanakan kod JavaScript untuk menambah dua nombor yang diberikan dalam bentuk senarai terpaut dan mengembalikan hasilnya dalam bentuk senarai terpaut. Kami melaksanakan dua kaedah dengan kerumitan masa dan ruang O(N).

Atas ialah kandungan terperinci Program JavaScript menambah dua nombor yang diwakili oleh senarai terpaut - Persediaan 1. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!