82. Remove Duplicates from Sorted List II

Problem Statement

link: LeetCode.cn LeetCode 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.

Example:

Input: head = [1,2,3,3,4,4,5] Output: [1,2,5]

Input: head = [1,1,1,2,3] Output: [2,3]

Solution Approach

Use a dummy node to handle edge cases and traverse the list, skipping nodes with duplicate values by linking to the next non-duplicate node.

Algorithm

1. Use a Dummy Node: Create a dummy node before the head to handle edge cases, ensuring the head can be easily removed if it’s a duplicate.
2. Traverse and Detect Duplicates: Use a pointer to traverse the list, checking consecutive nodes for duplicates. When duplicates are found, skip all nodes with the duplicate value.
3. Link Non-Duplicate Nodes: Adjust pointers to link the current node to the next distinct node, effectively removing all duplicates from the list.

Implement

    # Definition for singly-linked list. # class ListNode: #     def __init__(self, val=0, next=None): #         self.val = val #         self.next = next class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        #prev_val == cur.val:  cur = cur.next 
        # 1 2           3 4 4
        #.  cur
        if not head:
            return head

        dummy = ListNode(0, head)
        cur = dummy
        while cur.next and cur.next.next:
            if cur.next.val == cur.next.next.val:
                pre = cur.next.val
                while cur.next and cur.next.val == pre:
                    cur.next = cur.next.next 
            else:
                cur = cur.next
        return dummy.next
        

    
    

Twitter  facebook  Email