Program Javascript untuk mengalih keluar pendua daripada senarai terpaut yang diisih

Senarai terpaut ialah struktur data linear Kami diberi senarai terpaut diisih yang terdiri daripada integer. Terdapat beberapa nombor yang mungkin berulang atau berulang dan kami perlu mengeluarkannya. Memandangkan senarai terpaut yang diberikan diisih, kita hanya boleh mengulanginya dan menggunakan gelung sementara kita boleh mengalih keluar nod pendua daripadanya. Kami akan melaksanakan kod yang sesuai melalui perbincangan tentang kerumitan masa dan ruang untuk lebih memahami logiknya.

Contoh

Given linked list is: 1-> 2 -> 2 -> 3 -> 4 -> 4 -> 4 -> 5 -> 5 -> 5-> 6-> null
Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Penjelasan - Senarai terpaut yang diberikan diisih yang memudahkan untuk mencari elemen pendua dan kami boleh mengalih keluarnya dengan melangkau jika ia sama dengan nilai sebelumnya.

Jom lihat cara kod berfungsi

Kaedah

Kami akan mengikuti langkah-langkah di bawah untuk menyelesaikan isu -

• Pertama, kami akan mencipta kelas untuk menyediakan struktur untuk nod senarai terpaut.

• Kedua, kami akan mencipta fungsi yang mencetak senarai terpaut dan menambah nod baharu pada senarai terpaut sedia ada.

• Kami akan mencipta fungsi untuk melepasi kepala senarai terpaut dari mana kami ingin mengalih keluar elemen pendua dan ia akan mengembalikan kepala senarai terpaut baharu.

• Pertama, kami akan menyemak sama ada senarai dipautkan kosong atau jika saiznya bersamaan dengan 1. Dalam kes ini kita kembalikan kepala seperti sedia ada.

• Kami akan mencipta dua pembolehubah, satu menunjukkan kepala dan satu lagi menunjukkan nod kepala seterusnya.

• Jika nilai nod semasa dan nod seterusnya adalah sama, maka kami akan mengalihkan nod seterusnya ke nod seterusnya dan mengemas kini alamat nod seterusnya nod semasa.

• Jika tidak, kita beralih ke nod seterusnya dan mengalihkan nod seterusnya ke nod seterusnya.

• Akhirnya kami akan kembali ke pengepala dan mencetak nilai yang ada di dalamnya.

Contoh

Mari kami melaksanakan langkah-langkah yang diberikan dalam kod untuk pemahaman yang lebih baik

// class to provide structure to linked list node
class Node{
   constructor(val){
      this.value = val
      this.next = null
   }
}
// function to print the linked list
function print(head){
   var temp = head;
   if(head == null){
      console.log("The given linked list is empty");
   } else {
      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){
   var new_node = new Node(data);
   if(head == null){
      head = new_node
      return new_node
   } else {
      tail.next = new_node;
      return new_node
   }
}
// function to remove the duplicate numbers 
function removeDupli(head){
   // if linked list is empty 
   if(head == null){
      return head;
   }
   // if linked list is of size one 
   if(head.next == null){
      return head;
   }
   var temp = head
   var next = head.next
   while(next != null){
      if(temp.value == next.value){
         next = next.next;
         temp.next = next;
      } else {
         next = next.next;
         temp = temp.next;
      }
   }
   return head;
}
// defining linked list
var head  = new Node(1)
var tail  = head
tail = add(2,head, tail)
tail = add(2,head, tail)
tail = add(3,head, tail)
tail = add(4,head, tail)
tail = add(4,head, tail)
tail = add(4,head, tail)
tail = add(5,head, tail)
tail = add(5,head, tail)
tail = add(5,head, tail)
tail = add(6,head, tail)
console.log("The given linked list is: ")
print(head)
// calling function to remove duplicate elements 
head = removeDupli(head)
console.log("The Linked list after removal of duplicate integers is: ")
print(head)

Kerumitan masa dan ruang

Kerumitan masa kod di atas ialah O(N), dengan N ialah jumlah bilangan nod dalam senarai terpaut yang diberikan. Kerumitan masa adalah linear kerana kami hanya melintasi senarai terpaut sekali.

Kerumitan ruang kod di atas ialah O(1) kerana kami tidak menggunakan sebarang ruang tambahan.

Kesimpulan

Dalam tutorial ini, kami melaksanakan program JavaScript untuk mengalih keluar elemen pendua daripada senarai terpaut diisih yang diberikan. Memandangkan senarai terpaut diisih, semua elemen pendua bersebelahan antara satu sama lain dan boleh dialih keluar dengan mudah dengan melintasinya. Kerumitan masa program yang kami laksanakan ialah O(N) dan kerumitan ruang ialah O(1).

Atas ialah kandungan terperinci Program Javascript untuk mengalih keluar pendua daripada senarai terpaut yang diisih. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!