LeetCode — Remove Duplicates from Sorted List II

Problem Link: https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

Example of question

Problem Description: 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.

Approach Used: Linked-list, Iteration

Explanation: This question is a slight modification of a standard linked list question in which we have to keep a single element of each value and delete all the duplicates. In this question since we might have to delete the current node also if there are multiple nodes with the same value, we should at each point keep track of the previous node. Then we can simple readjust links to make the previous node (last node before the chain of duplicate nodes) point to the node after all the duplicate nodes. We’ll have to handle one more scenario when the first node itself has multiple duplicates. In this case, we will have to make the head point to the first node in the list which does not have duplicates. To check if the first node itself has duplicates we can simply see if the previous node is null or not. Because in the entire list only head node will have its previous node as null.

Code: (Java)

public ListNode deleteDuplicates(ListNode head) {
        //base case - empty list or single node (there can be no duplicates)
        if(head==null || head.next==null)
            return head;
        
        //storing head in another node so that original list is not lost
        ListNode temp = head; 
        //for storing previous node at each point
        ListNode prev = null;
        
        //since we will be comparing value of adjacent nodes we should ensure that both are not null
        while(temp!=null && temp.next!=null){
            //if duplicate found
            if(temp.val==temp.next.val){
                //move forward until non duplicate element found
                while(temp!=null && temp.next!=null && temp.val==temp.next.val)
                    temp = temp.next;
                
                //if previous is not null means we are not at head
                //so previous should point to next node after chain of duplicates
                if(prev!=null)
                    prev.next = temp.next;
                
                //else head needs to point to first non duplicate
                else
                    head = temp.next;
            }
            //else make previous equal to current node to move ahead with traversal
            else
                prev = temp;
            
            //increment current node for next set of nodes
            temp = temp.next;
        } 
        
        //return head node of updated list
        return head;
    }

Complexity:
Space complexity: O(1). Since we are only readjusting links and not even using recursion, no new memory allocation is required.
Time complexity: O(n). Since we will be visiting each node exactly once.
Here n is the number of nodes in the original linked list.