Given 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: 1->2->3->3->4->4->5
Output: 1->2->5
Example 2:
Input: 1->1->1->2->3
Output: 2->3
Solution:
class Solution
{
public:
ListNode *deleteDuplicates(ListNode *head)
{
if (head == NULL)
{
return head;
}
ListNode *p = head->next;
ListNode *q = head;
while (p != NULL)
{
if (q->val == p->val)
{
q->next = p->next;
p = p->next;
}
else
{
p = p->next;
q = q->next;
}
}
return head;
}
};
Time Complexity: O(n)
Type II:
Given 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: 1->2->3->3->4->4->5
Output: 1->2->5
Example 2:
Input: 1->1->1->2->3
Output: 2->3
Solution I: (Using HashSet)
class Solution
{
public:
ListNode *deleteDuplicates(ListNode *head)
{
if(head == NULL){return head;}
unordered_set<int> s;
ListNode *p = head->next;
ListNode *q = head;
while (p != NULL)
{
if (p->val == q->val)
{
s.insert(p->val);
q->next = p->next;
p = p->next;
}
else
{
q = q->next;
p = p->next;
}
}
p = head;
q = NULL;
while (p != NULL)
{
if (s.find(p->val) != s.end())
{
if (q != NULL)
{
q->next = p->next;
p = p->next;
}
else if(q == NULL)
{
head = p->next;
p = head;
}
}
else
{
q = p;
p = p->next;
}
}
return head;
}
};
Time Complexity: O(n) , Space Complexity: O(n)
Solution II:
class Solution
{
public:
ListNode *deleteDuplicates(ListNode *head)
{
if (head == NULL)
{
return head;
}
// Creating a Dummy node to check duplicates in head
ListNode* temp = new ListNode;
temp->next = head;
ListNode *p = head;
ListNode *q = temp;
while (p!=NULL)
{
while (p->next && p->val == p->next->val)
{
p = p->next;
}
if (q->next == p)
{
q = p;
}
else
{
q->next = p->next;
}
p = p->next;
}
//Pointing to dummy of next
head = temp->next;
return head;
}
};