Leetcode: Remove duplicates from sorted list II
Remove duplicate items from a linked list completely, including the original item.
The trick is to use two pointers and keep a pre_slow pointer which is initially set to None.
Upon discovering duplicates, move the fast pointer until either the end of the list or a non-duplicate
is seen and then set pre_slow.next to the next element. Then move every pointer to the next pointer.
The special case here is if the duplicates occur in the beginning. In this case, head itself needs to
be moved to fast and slow stays at the new head.
# 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]:
if head is None or head.next is None:
return head
pre_slow = None
slow = head
fast = head.next
while slow is not None and fast is not None:
if slow.val != fast.val:
pre_slow = slow
slow = slow.next
fast = slow.next
elif slow.val == fast.val:
while fast is not None and slow.val == fast.val:
fast = fast.next
if pre_slow is not None:
pre_slow.next = fast
slow = pre_slow.next
if slow is not None:
fast = slow.next
else:
# Special case: Move head to fast as all nodes were the same
head = fast
slow = head
if slow is not None:
fast = slow.next
return head