-
Notifications
You must be signed in to change notification settings - Fork 0
/
RemoveDuplicatesLinkedList.cpp
61 lines (54 loc) · 1.16 KB
/
RemoveDuplicatesLinkedList.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <cstdio>
#include <unordered_set>
using namespace std;
class ListNode {
public:
int val;
ListNode* next;
ListNode(int n) : val(n), next(NULL) {}
};
ListNode* remove(ListNode* head) {
if (!head || !head->next) return head;
ListNode* dummy = new ListNode(-1);
dummy->next = head;
unordered_set<int> hashT;
ListNode* ptr1 = dummy;
ListNode* ptr2 = ptr1->next;
while (ptr1) {
ptr2 = ptr1->next;
while (ptr2 && hashT.count(ptr2->val) > 0) ptr2 = ptr2->next;
if (ptr2) hashT.insert(ptr2->val);
ptr1->next = ptr2;
ptr1 = ptr1->next;
}
return dummy->next;
}
ListNode*
void Print(ListNode* head) {
while (head) {
std::cout << head->val << std::endl;
head = head->next;
}
}
int main() {
ListNode* p1 = new ListNode(1);
ListNode* p2 = new ListNode(3);
ListNode* p3 = new ListNode(1);
ListNode* p4 = new ListNode(3);
ListNode* p5 = new ListNode(9);
ListNode* p6 = new ListNode(6);
ListNode* p7 = new ListNode(1);
ListNode* p8 = new ListNode(3);
p1->next = p2;
p2->next = p3;
p3->next = p4;
p4->next = p5;
p5->next = p6;
p6->next = p7;
p7->next = p8;
Print(p1);
ListNode* head = remove(p1);
Print(head);
return 0;
}