16.Remove Duplicates from Sorted List

Type I

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;
    }
};

Time Complexity: O(n) , Space Complexity: O(1)