Leetcode Solution - Remove Duplicates from Sorted List II

 Que:- 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.

Link of Question :- https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/description/

Solution:-

#Complexity:-

Time Complexity = O(N)

Space Complexity = O(1)

#Approach:-

Here I have used the sentinel node. Sentinel nodes are specially designed

nodes that do not hold or refer to any data of the Singly LinkedList.

You can learn more about Sentinel node from here:-

https://www.geeksforgeeks.org/doubly-linked-list-using-sentinel-nodes/

#Code:-

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode() : val(0), next(nullptr) {}

 *     ListNode(int x) : val(x), next(nullptr) {}

 *     ListNode(int x, ListNode *next) : val(x), next(next) {}

 * };

 */

class Solution {

public:

    ListNode* deleteDuplicates(ListNode* head) {

        // Sentinel Node

        ListNode *sentinel = new ListNode(0, head);

        ListNode *prev = sentinel;

        while(head!=NULL)

        {

            if(head->next!=NULL && head->val==head->next->val)

            {

                while(head->next!=NULL && head->val==head->next->val)

                    head = head->next;

                prev->next = head->next;

            }

            else

            {

                prev = prev->next;

            }

            head = head->next;

        }

        return sentinel->next;

    }

};

Hope you like this blog. Please share it with your friends and comment your Suggestions.

Keep Learning, Keep Growing!