鏈表是線性數(shù)據(jù)結構，我們給出了一個由整數(shù)組成的排序鏈表。有一些數(shù)字可能重復或重復，我們必須將其刪除。由于給定的鏈表已排序，我們可以簡單地對其進行迭代，并使用 while 循環(huán)可以從中刪除重復的節(jié)點。我們將通過時間和空間復雜度的討論來實現(xiàn)適當?shù)拇a，以便更好地理解邏輯。
示例
Given linked list is: 1-> 2 -> 2 -> 3 -> 4 -> 4 -> 4 -> 5 -> 5 -> 5-> 6-> null Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
登錄后復制
說明 – 給定的鏈表是排序的，這使得很容易找到重復的元素，如果它們等于以前的值，我們可以通過跳過來刪除它們。
讓我們看看代碼的實現(xiàn)方式
方法
我們將按照以下步驟來解決問題 –
首先，我們將創(chuàng)建一個類來為鏈表的節(jié)點提供結構。
其次，我們將創(chuàng)建打印鏈表并向現(xiàn)有鏈表添加新節(jié)點的函數(shù)。
我們將創(chuàng)建一個函數(shù)來傳遞要從中刪除重復元素的鏈表的頭，它將返回新鏈表的頭。
首先，我們將檢查鏈表是否為空或者其大小是否等于 1。在這些情況下，我們將按原樣返回頭部。
我們將創(chuàng)建兩個變量，一個指示頭部，另一個指示頭部的下一個節(jié)點。
如果當前節(jié)點和下一個節(jié)點的值相等，那么我們會將下一個節(jié)點移動到下一個節(jié)點，并更新當前節(jié)點的下一個節(jié)點的地址。
否則，我們將移動到下一個節(jié)點并將下一個節(jié)點移動到其下一個節(jié)點。
最后我們將返回頭部并打印其中存在的值。
示例
讓我們在代碼中實現(xiàn)給定的步驟以便更好地理解
// 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 是給定鏈表中的節(jié)點總數(shù)。時間復雜度是線性的，因為我們只遍歷了鏈表一次。
上述代碼的空間復雜度為 O(1)，因為我們沒有使用任何額外的空間。
結論
在本教程中，我們實現(xiàn)了一個 JavaScript 程序，用于從給定的排序鏈表中刪除重復元素。由于鏈表是排序的，因此所有重復元素都彼此相鄰，并且可以通過遍歷它輕松刪除。我們實現(xiàn)的程序時間復雜度為O(N)，空間復雜度為O(1)。
以上就是用于從排序鏈接列表中刪除重復項的 Javascript 程序的詳細內(nèi)容，更多請關注www.92cms.cn其它相關文章！
