[Top Interview 150] 82. Remove Duplicates from Sorted List II

Solution)

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Base Case
        if not head: return None
        
        # Dummy Node
        dummy = ListNode(0, head)

        # dup's initial value is a value that 
        # a node cannot have in this problem
        prev, cur = dummy, head
        dup = -101
        while cur.next:
            # If a duplicate is found, save that value
            if cur.val == cur.next.val:
                dup = cur.val
            
            # If the current node's value is dup
            # Remove the current node
            if cur.val == dup:
                prev.next = cur.next

            # If not just update prev to its next node                
            else:
                prev = prev.next

            cur = cur.next

        # Check the last node
        if cur.val == dup:
            prev.next = None
        
        return dummy.next

 
Problem: LeetCode
 
Time Complexity: O(n)
Space Complexity: O(1)
 

Explanation)

I'm sure you already know what to do but just don't know how to code it (if you don't know what to do, that's fine!).
So I'll start explaining in steps right away.
 

1. Base Case & Initialization)

If a linked list doesn't exist, you have nothing to do so return None.
 
Make a dummy node that will be followed by head. This allows us to access the start of the linked list.
 

def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 1. Base Case & Initialization
        if not head: return None
        
        dummy = ListNode(0, head)

 

2. If there is a duplicate)

Variable prev indicates the node before the current node.
Variable cur indicates the the current node.
 
Variable dup indicates an integer value of duplicate nodes. Its initial value is -101, which is a value that a node cannot have in this linked list (check the constraints of the problem).
 
While iterating the linked list, we'll check if the current node's value is the same as the next node's value. If it does, it means that they are duplicates. So we'll save that value to dup.
 

def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 1. Base Case & Initialization
        if not head: return None
        
        dummy = ListNode(0, head)
	
        # 2. If there is a duplicate
        prev, cur = dummy, head
        dup = -101
        while cur.next:
            if cur.val == cur.next.val:
                dup = cur.val

 

3. If the current node is one of the duplicate nodes)

If the current node is a duplicate, we need to delete that.
Deleting a node from a linked list means that we need to adjust the surrounding nodes.
 
Knowing what the previous node is, we can make prev.next as cur.next. We're basically skipping the current node.
 

def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 1. Base Case & Initialization

        # 2. If there is a duplicate
        prev, cur = dummy, head
        dup = -101
        while cur.next:
            if cur.val == cur.next.val:
                dup = cur.val
            
            # 3. If the current node is one of the duplicate nodes
            if cur.val == dup:
                prev.next = cur.next

 

4. If the current node isn't a duplicate)

When cur was a duplicate, prev stayed at its place because we needed the previous node's information to connect future nodes to that previous node.
 
However, if cur isn't a duplicate, we need to update prev as well because we don't need that information anymore.
 
Once prev is updated, it's time to update cur. cur is moved to its next node every iteration because we need to iterate the linked list no matter what.
 

def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 1. Base Case & Initialization

        # 2. If there is a duplicate
        prev, cur = dummy, head
        dup = -101
        while cur.next:
            if cur.val == cur.next.val:
                dup = cur.val
            
            # 3. If the current node is one of the duplicate nodes
            if cur.val == dup:
                prev.next = cur.next
                
            # 4. If the current node isn't a duplicate    
            else:
                prev = prev.next

            cur = cur.next

 

5. Check the last node)

According to our while-loop condition, we're leftover with the last node. We also need to check if that last node is one of the duplicates.
 
If it is, our prev node will have its next as None.
 
Now we deleted all the duplicates, so we return the start of the linked list.
 

def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 1. Base Case & Initialization

        # 2. If there is a duplicate
        # 3. If the current node is one of the duplicate nodes
        # 4. If the current node isn't a duplicate    

        # 5. Check the last node
        if cur.val == dup:
            prev.next = None
        
        return dummy.next

 
 
 
I wasn't so sure how to breifly explain this because the logic itself is very simple. You just need to know how to code it. There is a much cleaner way when extra space is used, but I wanted to solve it with constant space, and the solution got a bit messy.