Unexpected results with two pointer algorithm to remove duplicates from sorted linked list

Question

I am solving Leetcode 83. Remove Duplicates from Sorted List:

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

Constraints

• The number of nodes in the list is in the range [0, 300].
• -100 <= Node.val <= 100
• The list is guaranteed to be sorted in ascending order.

I came up with a two pointer solution and for some reason it doesn't work / produces unexpected results. What's wrong with my code? I'm not interested in the right code, but actually want to understand what is wrong with mine.

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None

        #: Intutive O(n) single pointer:#
        # curr = head
        # while curr.next:
        #     if curr.val == curr.next.val:
        #         curr.next = curr.next.next
        #     else: curr = curr.next
        # return head

        #. T.C = O(n), S.C: O(1)
        #. Uses only one temp value
        #. Goes through each variable and skips the node with same value.
        #+ we can improve this as we could try to skip multiple duplicate nodes at once

        #: Two pointer :#

        slow, fast = head , head.next
        while fast != None:
            if slow == fast:
                fast=fast.next
                slow.next = fast
            else:
                fast = fast.next
                slow = slow.next
        slow.next = None
        return head

I am implementing two pointers, namely slow and fast, checking for head being null, then checking if there is a duplicate using the fast pointer. If yes, I am moving the fast pointer to the next node and making slow.next point to the next node directly. For reason this is not working. Let me know what is actually happening in my code.

Answer 1

What you describe as intended algorithm is a correct algorithm, but the implementation has one issue:

           if slow == fast:

This checks whether slow and fast reference the same node. This will never be the case, as fast is walking ahead of slow and referencing a different node. What you really want is to check whether they have the same value:

           if slow.val == fast.val:

With this change it should work.