資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究從無序連結串列中移除重複元素的 JavaScript 程式
連結串列是一種線性資料結構，由節點組成，每個節點以非連續的方式儲存在記憶體中。節點透過儲存下一個節點的地址來連線。我們得到一個連結串列，它將以隨機方式儲存一些整數，而不是以排序的方式儲存。任務是找到連結串列中重複的元素，並且我們必須刪除重複的元素。我們將看到正確的程式碼和解釋。
在這個問題中，我們將保留連結串列元素的第一個副本，並刪除之前出現在連結串列中的元素或不是同一組重複元素中的第一個元素。
例如 -
Given linked list is 1 -> 5 -> 5 -> 2 -> 7 -> 1 -> 2 -> 6 -> 5 -> 7 -> 7-> null. Output: 1 -> 5 -> 2 -> 7 -> 6 -> null.
在給定的連結串列中，只有 5 個元素是唯一的，即 1、5、2、7 和 6，其他的與它們相似，因此我們將刪除重複的元素。
示例：樸素方法
在這種方法中，我們將使用兩個迴圈遍歷給定的列表。
// 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;
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){
return tail.next = new Node(data)
}
// function to remove the duplicate numbers
function removeDupli(head){
if(head == null || head.next == null){
return head;
}
var temp = head.next;
while(temp != null) {
var temp2 = head;
while(temp2 != temp && temp2.value != temp.value){
temp2 = temp2.next;
}
if(temp2 == temp) {
temp = temp.next;
} else {
while(temp2.next != temp) {
temp2 = temp2.next;
}
temp2.next = temp.next;
temp = temp.next;
}
}
return head;
}
// defining linked list
var head = new Node(1)
var tail = head
tail = add(5,head, tail)
tail = add(5,head, tail)
tail = add(2,head, tail)
tail = add(7,head, tail)
tail = add(1,head, tail)
tail = add(2,head, tail)
tail = add(6,head, tail)
tail = add(5,head, tail)
tail = add(7,head, tail)
tail = add(7,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 the removal of duplicate integers is: ")
print(head)
上述程式碼的時間複雜度為 O(N*N)，空間複雜度為 O(1)。
示例：使用雜湊
在這種方法中，我們將使用雜湊集來查詢重複元素
// 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;
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){
return tail.next = new Node(data)
}
// function to remove the duplicate numbers
function removeDupli(head){
if(head == null || head.next == null){
return head;
}
var temp = head.next;
var prev = head;
var myset = new Set()
myset.add(head.value);
while(temp != null){
if(myset.has(temp.value)){
prev.next = temp.next;
} else {
prev= prev.next;
myset.add(temp.value);
}
temp = temp.next;
}
return head;
}
// defining linked list
var head = new Node(1)
var tail = head
tail = add(5,head, tail)
tail = add(5,head, tail)
tail = add(2,head, tail)
tail = add(7,head, tail)
tail = add(1,head, tail)
tail = add(2,head, tail)
tail = add(6,head, tail)
tail = add(5,head, tail)
tail = add(7,head, tail)
tail = add(7,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*log(N))，空間複雜度為 O(1)。
結論
在本教程中，我們實現了雙指標和雜湊技術來從給定的連結串列中刪除重複元素。樸素或雙指標方法的時間複雜度為二次或 O(N*N)，而雜湊的時間複雜度約為線性或帶對數因子的 O(N*log(N))。
更新於: 2023年4月12日
185 次檢視
廣告