Remove duplicate elements from an un-sorted linked list.
Example:
Input: 1->2->1->4->2->5->4->NULL
Output: 1->2->4->5->NULLApproach
Java
import java.util.HashSet;
public class RemoveDuplicatesFromUnSortedList {
public static void main(String[] args) {
ListNode l = new ListNode(1);
l.next = new ListNode(2);
l.next.next = new ListNode(1);
l.next.next.next = new ListNode(4);
l.next.next.next.next = new ListNode(2);
l.next.next.next.next.next = new ListNode(5);
l.next.next.next.next.next.next = new ListNode(4);
ListNode node = removeDuplicateElement(l);
System.out.println("After Removing :");
linkedListTraversal(node);
}
private static void linkedListTraversal(ListNode node) {
while (node != null) {
System.out.print(node.val + " ");
node = node.next;
}
}
public static ListNode removeDuplicateElement(ListNode head) {
HashSet<Integer> set = new HashSet<Integer>();
// If list is null
if (head == null) {
return head;
}
ListNode root = head;
ListNode prev = root;
// Iterate till end of list
while (root != null) {
if (set.contains(root.val)) {
prev.next = root.next;
}
set.add(prev.val);
prev = root;
root = root.next;
}
return head;
}
}
class ListNode implements Comparable<ListNode> {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
@Override
public int compareTo(ListNode o) {
if (this.val == o.val)
return 0;
else if (this.val > o.val)
return 1;
else
return -1;
}
}
C++
#include <bits/stdc++.h>
using namespace std;
//Struture of node
struct Node
{
int data;
Node *next;
Node(int data)
{
this->data=data;
this->next=NULL;
}
};
//function to traverse(print) a linked
//list
void linkedListTraversal(Node *head)
{
Node *temp=head;
//iterate till we reach end of the linked
//list
while(temp!=NULL)
{
//print the current
//node data
cout<<temp->data<<" ";
//move to next node
temp=temp->next;
}
}
Node *removeDuplicateElement(Node *head)
{
set<int> set;
// If list is null
if (head ==NULL) {
return head;
}
Node *root = head;
Node *prev = root;
// Iterate till end of list
while (root != NULL) {
if (set.find(root->data)!=set.end()) {
prev->next = root->next;
}
set.insert(prev->data);
prev = root;
root = root->next;
}
return head;
}
int main()
{
Node * l = new Node(1);
l->next = new Node(2);
l->next->next = new Node(1);
l->next->next->next = new Node(4);
l->next->next->next->next = new Node(2);
l->next->next->next->next->next = new Node(5);
l->next->next->next->next->next->next = new Node(4);
Node *node = removeDuplicateElement(l);
cout<<"After Removing :";
linkedListTraversal(node);
}
No comments:
Post a Comment