数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究用于从已排序链表中删除重复项的 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)。
更新于：2023年4月12日
286 次浏览
广告