-
Notifications
You must be signed in to change notification settings - Fork 0
/
removeSortedList2nd.cpp
72 lines (63 loc) · 2.22 KB
/
removeSortedList2nd.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
62
63
64
65
66
67
68
69
70
71
72
82. Remove Duplicates from Sorted List II
Medium
7.1K
187
Companies
Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.
Example 1:
Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]
Example 2:
Input: head = [1,1,1,2,3]
Output: [2,3]
//CODE
//Recursion Method
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
// when not found or last element
if (head==NULL || head->next==NULL){
return head;
}
bool j = false;
while (head->next!=NULL && head->val == head->next->val){
j = true;
head->next = head->next->next;
}
if (j){
head = deleteDuplicates(head->next);
return head;
}
head->next = deleteDuplicates(head->next);
return head;
}
};
// Iterratively Method
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
// create a fake node that acts like a fake head of list pointing to the original head...
ListNode* fake = new ListNode(0);
// fake node points to the original head...
fake->next = head;
ListNode* pre = fake; //pointing to last node which has no duplicate...
ListNode* curr = head; // To traverse the linked list...
// Now we traverse nodes and do the process...
while (curr != NULL) {
// Create a loop until the current and previous values are same, keep updating curr...
while (curr->next != NULL && pre->next->val == curr->next->val)
curr = curr->next;
// if curr has non-duplicate value, move the pre pointer to next node...
if (pre->next == curr)
pre = pre->next;
// If curr is updated to the last duplicate value, discard it & connect pre and curr->next...
else
pre->next = curr->next;
// Move curr forward...
// In next iteration, we still need to check whether curr points to duplicate value...
curr = curr->next;
}
// Return the linked list...
return fake->next;
}
};