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