[LeetCode/릿코드] 83. Remove Duplicates from Sorted list

Clarify the problem

Problem: Remove all duplicates and return the head of the cleaned linked list
Input: root node of a sorted linked list
Output: root node of the cleaned linked list

Example:

1->1->2->2
-> 1-> 2

Clarification:

• What should be returned if the input node is None?
  -> return None
• What value can each node have?
  -> -100 <= value <= 100

Design a solution

Idea

• A simple traversal approach is a good fit for this problem with linear time complexity.
• We will use a while loop to advance toward the end of the linked list.
• At each step, we compare the current node with the previous node. If both have the same value, we connect the previous node to the next node.
• We will use a dummy node at the front to allow a uniform previous-current comparison.

Algorithm

1. Early termination: if the root node is None, return None.
2. Initialize the current node
3. Create a dummy node with a value of None, connect it to the given root node, and set pre to the dummy node
4. While the current node is not None
   • If the value of current node is the same as the value of the previous node, set pre.next to cur.next
   • Otherwise, move pre to the current node
   • Advance cur to the next node
5. Return the dummy.next

Implement the Code

class Solution:
    def deleteDuplicates(self, head):

        if not head:
            return None
        
        # initialize
        cur = head
        dummy = ListNode(None, cur)
        pre = dummy

        # remove duplicates
        while cur: 
            if pre.val == cur.val:
                pre.next = cur.next
            
            # Advance cursors
            else:
                pre = cur # NOT moving pre when duplicate 
            cur = cur.next
        
        # return the new head node
        return dummy.next

Self Review (Eye Test)

We should move pre cursor only when pre.val is differnt from cur.val. However, we shouldn't move pre after removing duplicates. If pre were moved to cur and next node were also a duplicate, the link would be broken.

The above solution adopts a one-step-advance approach. An alternative appoach could be to advance directly to the next non-duplicate node. However, I think using a single while loop is safer and easier to control the flow.

original version

        while cur: 
            if pre.val == cur.val:
                pre.next = cur.next
            
            # Advance cursors
            else:
                pre = cur # NOT moving pre when duplicate 
            cur = cur.next

alternaive version

        # traverse a linked list
        while cur: 
            
            # remove duplciate
            while cur and pre.val == cur.val:
                cur = cur.next
            pre.next = cur

            # Advance cursors
            if not cur:
                break 
            else:
                pre = cur
                cur = cur.next

Check Performance

Time Complexity: O(n), where n is the number of nodes in a linked list
Space Complexity: O(1), use three variables and mutate a linked list

Polish the solution