Remove Duplicates from Sorted List II — LeetCode 82 Python Solution

The problem

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]

Python solution

# 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]:
        dummy = pre = ListNode(next=head)
        cur = head
        while cur:
            while cur.next and cur.next.val == cur.val:
                cur = cur.next
            if pre.next == cur:
                pre = cur
            else:
                pre.next = cur.next
            cur = cur.next
        return dummy.next

Complexity

Pattern: Linked List

Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 82. Remove Duplicates from Sorted List II is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Linked List.

The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.

Related problems