Program JavaScript untuk menulis fungsi untuk mendapatkan nod Nth dalam senarai terpaut

Senarai terpaut ialah struktur data linear di mana semua nod disambungkan antara satu sama lain dengan menyimpan alamat nod seterusnya. Mencari nod ke-n dalam senarai terpaut bermakna mendapatkan nilai nod ke-n dalam senarai terpaut yang diberikan, yang boleh dilakukan dengan kaedah berulang dan rekursif.

Contoh

Given linked list: 
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
Node to find: 3

Output

3

Penjelasan: Nilai nod ketiga ialah 3.

Kaedah berulang

Dalam kaedah ini, kami akan terus melintasi senarai terpaut menggunakan gelung while sehingga kami mencapai nod terakhir atau nod yang dikehendaki.

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 find the nth node 
function findNode(head, node){
   var temp = head;
   while(node > 1 && temp != null){
      node--;
      temp = temp.next;
   }
   return temp;
}

// defining linked list
var head  = new Node(1)
var tail  = head
tail = add(2,head, tail)
tail = add(3,head, tail)
tail = add(4,head, tail)
tail = add(5,head, tail)
tail = add(6,head, tail)
tail = add(7,head, tail)
tail = add(8,head, tail)

// printing linked list 
console.log("The given linked list is: ")
print(head)

// defining node to get 
var node = 5;

// calling function to get the nth node; 
var nth_node = findNode(head,node)
if(nth_node == null){
   console.log("The given linked list does not have the Nth Node");
}
else{
   console.log("The value present at the nth node is: " + nth_node.value);
}

Output

The given linked list is: 
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> null
The value present at the nth node is: 5

Kerumitan masa dan ruang

Kerumitan masa kod di atas ialah O(N), dengan N ialah saiz senarai terpaut yang diberikan. Nombor yang diberikan di sini mungkin lebih kecil daripada saiz senarai terpaut yang diberikan, tetapi dalam kes yang paling teruk, kami hanya akan merentasi panjang senarai terpaut.

Di sini kami tidak menggunakan sebarang ruang tambahan, yang bermaksud kerumitan masa kod di atas ialah O(1).

Kaedah rekursif

Dalam kaedah ini, kami akan menggunakan panggilan rekursif dan bukannya gelung sementara untuk melintasi senarai terpaut dan melaksanakan logik sebelumnya.

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 find the nth node 
function findNode(head, node){
   if(node == 1){
      return head;
   }
   else if(head == null){
      return null;
   }
   else{
      return findNode(head.next, node-1);
   }
}

// defining linked list
var head  = new Node(1)
var tail  = head
tail = add(2,head, tail)
tail = add(3,head, tail)
tail = add(4,head, tail)
tail = add(5,head, tail)
tail = add(6,head, tail)
tail = add(7,head, tail)
tail = add(8,head, tail)

// printing linked list 
console.log("The given linked list is: ")
print(head)

// defining node to get 
var node = 9;

// calling function to get the nth node; 
var nth_node = findNode(head,node)
if(nth_node == null){
   console.log("The given linked list does not have the " + node + " number of nodes");
}
else{
   console.log("The value present at the nth node is: " + nth_node.value);
}

Output

The given linked list is: 
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> null
The given linked list does not have the 9 number of nodes

Kerumitan masa dan ruang

Kerumitan masa dan ruang kod di atas adalah sama, kedua-duanya adalah O(N), dengan N ialah bilangan nod dalam senarai terpaut yang diberikan. Ruang di sini adalah disebabkan oleh panggilan rekursif.

Kesimpulan

Dalam tutorial ini, kami melaksanakan program JavaScript untuk mencari nod ke-n dalam senarai terpaut yang diberikan. Jika nod ke-n tidak wujud, maka kita mencetak bahawa ia tidak wujud, jika tidak, kita mencetak nilai yang wujud pada nod tersebut. Kami melaksanakan dua kaedah, satu adalah berulang menggunakan gelung while dan satu lagi kaedah rekursif. Kerumitan masa kedua-duanya adalah O(N), tetapi lelaran adalah lebih baik kerana ia tidak memerlukan ruang tambahan.

Atas ialah kandungan terperinci Program JavaScript untuk menulis fungsi untuk mendapatkan nod Nth dalam senarai terpaut. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!