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)。