Remove Duplicates From Sorted List Ii - Leetcode Solution

Problem Statement:

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Example:

Input: 1->2->3->3->4->4->5 Output: 1->2->5

Input: 1->1->1->2->3 Output: 2->3

Approach:

The approach to solving this problem is fairly simple. We will create a new linked list and traverse the input linked list. We will add only those nodes to the new linked list which have non-duplicate values. We will also keep track of duplicates by using a flag. Whenever we find a duplicate node, we will set the flag to true and skip the duplicate nodes. When we find a non-duplicate node, we will add it to the new linked list only if the flag is false, otherwise we will discard it.

Algorithm:

1. Create a dummy node and assign it the value of -1 as it will never be used. We will use this node to return the new linked list.
2. Create two pointers, 'prev' and 'curr', and initialize them to the dummy node.
3. Create a boolean flag 'isDuplicate' and set it to false.
4. Traverse the input linked list using the 'curr' pointer.
5. If the current node has a non-duplicate value, then check the 'isDuplicate' flag. If it is false, add the node to the new linked list. If it is true, then discard the node.
6. If the current node has a duplicate value, set the 'isDuplicate' flag to true and keep advancing the 'curr' pointer to skip all the duplicate nodes.
7. Once all the nodes have been traversed, return the new linked list.

Code:

/**

• Definition for singly-linked list.

• struct ListNode {

• int val;
  

• ListNode *next;
  

• ListNode(int x) : val(x), next(NULL) {}
  

• }; / class Solution { public: ListNode deleteDuplicates(ListNode* head) {

   ListNode* dummy = new ListNode(-1); // Create a dummy node
   ListNode* prev = dummy;
   ListNode* curr = head;
   bool isDuplicate = false; // Flag to track duplicates
   
   while (curr != NULL) {
       
       if (curr->next != NULL && curr->val == curr->next->val) { // Check for duplicate value
           isDuplicate = true;
           curr = curr->next;
           continue;
       }
       
       if (isDuplicate) { // Skip nodes with duplicate values
           isDuplicate = false;
           curr = curr->next;
       }
       else { // Add nodes with non-duplicate values to the new linked list
           prev->next = curr;
           prev = prev->next;
           curr = curr->next;
       }
   }
   
   prev->next = NULL; // Set the last node to null
   return dummy->next; // Return the new linked list
  

  } };

Complexity Analysis:

Time complexity: O(n), where n is the number of nodes in the input linked list. We traverse the linked list once.

Space complexity: O(1). We are not using any extra space to store the input or output. We are only using constant space to store the pointers and the boolean flag.

1