Das JavaScript-Programm fügt zwei Zahlen hinzu, die durch eine verknüpfte Liste dargestellt werden – Setup 1

Das Addieren zweier Zahlen ist eine einfache Aufgabe, kann jedoch schwierig sein, wenn die Zahlen in Form einer verknüpften Liste angegeben werden. Jeder Knoten der verknüpften Liste enthält fortlaufend vom ersten bis zum letzten Knoten die Nummer der Zahl, die er darstellt. Wir erhalten zwei verknüpfte Listen, die zwei verschiedene Zahlen darstellen, müssen diese addieren und die dritte Zahl in Form einer verknüpften Liste zurückgeben.

Eintreten

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

Ausgabe

4 -> 4 -> 7 -> null

Erklärung: Da die erste Zahl 123, die zweite Zahl 324 und ihre Summe 447 ist, geben wir sie in Form einer verknüpften Liste zurück.

Umstellung auf digitale Methode

Bei dieser Methode konvertieren wir zunächst die gegebene Zahl von der verknüpften Listendarstellung in die Ganzzahlform und wenden dann die Additionsoperation an. Danach wandeln wir das Ergebnis in eine verknüpfte Liste um und kehren schließlich zurück, um die in der verknüpften Antwortliste vorhandenen Daten auszudrucken.

Beispiel

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

Ausgabe

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

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität des obigen Codes beträgt (M+N), wobei M und N die Größen der angegebenen verknüpften Liste sind.

Die räumliche Komplexität des obigen Codes beträgt O(N), da wir eine neue verknüpfte Liste erstellen.

Anders

Bei dieser Methode fügen wir verknüpfte Listenelemente hinzu, indem wir vom Ende zum ersten Knoten durchlaufen, bis der erste verknüpfte Listenwert Null wird. Wenn einmal Null wird, setzen Sie seinen Wert auf Null und bewegen Sie sich, bis beide Null werden.

Beispiel

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

Ausgabe

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

Fazit

In diesem Tutorial haben wir JavaScript-Code implementiert, um zwei in Form einer verknüpften Liste angegebene Zahlen zu addieren und das Ergebnis in Form einer verknüpften Liste zurückzugeben. Wir haben zwei Methoden mit O(N) Zeit- und Raumkomplexität implementiert.

Das obige ist der detaillierte Inhalt vonDas JavaScript-Programm fügt zwei Zahlen hinzu, die durch eine verknüpfte Liste dargestellt werden – Setup 1. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!