数据结构
网络
关系型数据库管理系统
操作系统
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 次查看
广告