用於從排序連結清單中刪除重複項的 Javascript 程序

鍊錶是線性資料結構，我們給出了一個由整數組成的排序鍊錶。有一些數字可能重複或重複，我們必須將其刪除。由於給定的鍊錶已排序，我們可以簡單地對其進行迭代，並使用 while 循環可以從中刪除重複的節點。我們將透過時間和空間複雜度的討論來實現適當的程式碼，以便更好地理解邏輯。

範例

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

說明 - 給定的鍊錶是排序的，這使得很容易找到重複的元素，如果它們等於先前的值，我們可以透過跳過來刪除它們。

讓我們看看程式碼的實作方式

方法

我們將按照以下步驟來解決問題 -

• 首先，我們將建立一個類別來為鍊錶的節點提供結構。

• 其次，我們將建立列印鍊錶並向現有鍊錶新增節點的函數。

• 我們將建立一個函數來傳遞要從中刪除重複元素的鍊錶的頭，它將傳回新鍊錶的頭。

• 首先，我們將檢查鍊錶是否為空或其大小是否等於 1。在這些情況下，我們將按原樣返回頭部。

• 我們將建立兩個變量，一個指示頭部，另一個指示頭部的下一個節點。

• 如果目前節點和下一個節點的值相等，那麼我們會將下一個節點移到下一個節點，並更新目前節點的下一個節點的位址。

• 否則，我們將移動到下一個節點並將下一個節點移動到其下一個節點。

• 最後我們將返回頭部並列印其中存在的值。

範例

讓我們在程式碼中實現給定的步驟以便更好地理解

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

時間與空間複雜度

上述程式碼的時間複雜度為 O(N)，其中 N 是給定鍊錶中的節點總數。時間複雜度是線性的，因為我們只遍歷了鍊錶一次。

上述程式碼的空間複雜度為 O(1)，因為我們沒有使用任何額外的空間。

結論

在本教程中，我們實作了一個 JavaScript 程序，用於從給定的排序鍊錶中刪除重複元素。由於鍊錶是排序的，因此所有重複元素都彼此相鄰，並且可以透過遍歷它輕鬆刪除。我們實現的程式時間複雜度為O(N)，空間複雜度為O(1)。

以上是用於從排序連結清單中刪除重複項的 Javascript 程序的詳細內容。更多資訊請關注PHP中文網其他相關文章！