Remove Duplicate

/***
2.1 Write code to remove duplicates form an unsorted linked list.
How would you solve this problem if a temporrary buffer is not allowed?
1) in place -- two pointer
p1 = p1->next;
p1->next != nullptr should be put before p1 != nullptr
2) using temp buffer: hashtable,, set...
***/

#include<iostream>
//#include<set>

using namespace std;

// in place
struct node {
int val;
node *next;
};

void removeDuplicate(node *n) {
node *p1, *p2;
p1 = n;

while(p1 != nullptr && p1->next != nullptr) {
p2 = p1;
while(p2 != nullptr && p2->next != nullptr) {
if(p2->next->val == p1->val) {
p2->next = p2->next->next;
}
p2 = p2->next;
}
p1 = p1->next;
}
}

void main () {
node n1, n2, n3, n4, n5;
n1.val = 1;
n1.next = &n2;
n2.val = 2;
n2.next = &n3;
n3.val = 1;
n3.next = &n4;
n4.val = 3;
n4.next = &n5;
n5.val = 2;
n5.next = nullptr;

removeDuplicate(&n1);

node *p1;
p1 = &n1;
while (p1 != nullptr)
{
cout<<p1->val<<"  ";
p1 = p1->next;
}

}

Comments

Popular posts from this blog

Sudoku

Longest prefix matching - trie

Climbing Stairs