5

Javascript Program For Removing Duplicates From An Unsorted Linked List

 11 months ago
source link: https://www.geeksforgeeks.org/javascript-program-for-removing-duplicates-from-an-unsorted-linked-list/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Javascript Program For Removing Duplicates From An Unsorted Linked List

Given an unsorted Linked List, the task is to remove duplicates from the list. 

Examples:

Input: linked_list = 12 -> 11 -> 12 -> 21 -> 41 -> 43 -> 21 
Output: 12 -> 11 -> 21 -> 41 -> 43 
Explanation: Second occurrence of 12 and 21 are removed.

Input: linked_list = 12 -> 11 -> 12 -> 21 -> 41 -> 43 -> 21 
Output: 12 -> 11 -> 21 -> 41 -> 43 

Naive Approach to Remove Duplicates from an Unsorted Linked List:

The most simple approach to solve this, is to check each node for duplicate in the Linked List one by one. 

Below is the Implementation of the above approach:

  • Javascript
// Javascript program to remove duplicates from unsorted
// linked list
var head;
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
/*
* Function to remove duplicates from an unsorted linked list
*/
function remove_duplicates() {
var ptr1 = null, ptr2 = null, dup = null;
ptr1 = head;
/* Pick elements one by one */
while (ptr1 != null && ptr1.next != null) {
ptr2 = ptr1;
/*
* Compare the picked element with rest of the elements
*/
while (ptr2.next != null) {
/* If duplicate then delete it */
if (ptr1.data == ptr2.next.data) {
/* sequence of steps is important here */
dup = ptr2.next;
ptr2.next = ptr2.next.next;
} else /* This is tricky */ {
ptr2 = ptr2.next;
}
}
ptr1 = ptr1.next;
}
}
function printList( node) {
while (node != null) {
console.log(node.data + " ");
node = node.next;
}
}
head = new Node(10);
head.next = new Node(12);
head.next.next = new Node(11);
head.next.next.next = new Node(11);
head.next.next.next.next = new Node(12);
head.next.next.next.next.next = new Node(11);
head.next.next.next.next.next.next = new Node(10);
console.log("Linked List before removing duplicates : <br/> ");
printList(head);
remove_duplicates();
console.log("<br/>");
console.log("Linked List after removing duplicates : <br/> ");
printList(head);
// This code contributed by aashish1995
Output 
Linked List before removing duplicates : <br/> 
10 
12 
11 
11 
12 
11 
10 
<br/>
Linked List after removing duplicates : <br/> 
10 
12 
11

Time Complexity: O(N2)
Auxiliary Space: O(1)

Remove duplicates from an Unsorted Linked List using Sorting:

Follow the below steps to Implement the idea:

Below is the implementation for above approach:

  • Javascript
// structure of a node in the linked list
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
// function to insert a node in the linked list
function push(head_ref, new_data) {
const new_node = new Node(new_data);
new_node.next = head_ref;
head_ref = new_node;
return head_ref;
}
// function to sort the linked list
function sortList(head) {
// pointer to traverse the linked list
let current = head;
let index = null;
// loop to traverse the linked list
while (current !== null) {
// loop to compare current node with all other nodes
index = current.next;
while (index !== null) {
// checking for duplicate values
if (current.data === index.data) {
// deleting the duplicate node
current.next = index.next;
index = current.next;
}
else {
index = index.next;
}
}
current = current.next;
}
}
// function to display the linked list
function printList(node) {
let str = "";
while (node !== null) {
str += node.data + " ";
node = node.next;
}
console.log(str);
}
// main function
let head = null;
head = push(head, 20);
head = push(head, 13);
head = push(head, 13);
head = push(head, 11);
head = push(head, 11);
head = push(head, 11);
console.log("Linked List before removing duplicates : ");
printList(head);
sortList(head);
console.log("Linked List after removing duplicates : ");
printList(head);
Output 
Linked List before removing duplicates : 
11 11 11 13 13 20 
Linked List after removing duplicates : 
11 13 20

Time Complexity: O(N log N)
Auxiliary Space: O(1)

Remove duplicates from an Unsorted Linked List using Hashing:

The idea for this approach is based on the following observations:

  • Traverse the link list from head to end.
  • For every newly encountered element, check whether if it is in the hash table:
    • if yes, remove it
    • otherwise put it in the hash table.
  • At the end, the Hash table will contain only the unique elements.

Below is the implementation of the above approach:

  • Javascript
// JavaScript program to remove duplicates
// from unsorted linkedlist
class node {
constructor(val) {
this.val = val;
this.next = null;
}
}
/*
Function to remove duplicates
from a unsorted linked list
*/
function removeDuplicate( head) {
// Hash to store seen values
var hs =  new Set();
/* Pick elements one by one */
var current = head;
var prev = null;
while (current != null) {
var curval = current.val;
// If current value is seen before
if (hs.has(curval)) {
prev.next = current.next;
} else {
hs.add(curval);
prev = current;
}
current = current.next;
}
}
/* Function to print nodes in a
given linked list */
function printList( head) {
while (head != null) {
console.log(head.val + " ");
head = head.next;
}
}
/*
* The constructed linked list is:
10->12->11->11->12->11->10
*/
start = new node(10);
start.next = new node(12);
start.next.next = new node(11);
start.next.next.next = new node(11);
start.next.next.next.next = new node(12);
start.next.next.next.next.next = new node(11);
start.next.next.next.next.next.next = new node(10);
console.log(
"Linked list before removing duplicates :<br/>"
);
printList(start);
removeDuplicate(start);
console.log(
"<br/>Linked list after removing duplicates :<br/>"
);
printList(start);
// This code is contributed by todaysgaurav
Output 
Linked list before removing duplicates :<br/>
10 
12 
11 
11 
12 
11 
10 
<br/>Linked list after removing duplicates :<br/>
10 
12 
11

Time Complexity: O(N), on average (assuming that hash table access time is O(1) on average).  
Auxiliary Space: O(N), As extra space is used to store the elements in the stack.

Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
You'll access excellent video content by our CEO, Sandeep Jain, tackle common interview questions, and engage in real-time coding contests covering various DSA topics. We're here to prepare you thoroughly for online assessments and interviews.
Ready to dive in? Explore our free demo content and join our DSA course, trusted by over 100,000 geeks! Whether it's DSA in C++, Java, Python, or JavaScript we've got you covered. Let's embark on this exciting journey together!
Last Updated : 28 Jun, 2023
Like Article
Save Article

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK