DEV Community

Cover image for Leetcode grind - Remove duplicates from a sorted linked list
matej
matej

Posted on

Leetcode grind - Remove duplicates from a sorted linked list

This one is pretty simple if there is just one duplicate, but if there are multiple, using just one pointer won't work, because we need to skip multiple duplicates.

Going on solution from z3r0gravity7 from here https://leetcode.com/problems/remove-duplicates-from-sorted-list/discuss/1589369/Python3-intuitive-O(n)-solution-with-seeking-pointer-faster-than-98-(with-explanation) ->

def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head == None or head.next == None: # handle edge cases where linked list has no or one nodes
            return head

        p = head # initialize current node pointer
        while p.next: # until we have reached the last node (where next pointer is None)
            seek = p.next # seek pointer is initialized to the node after current node (guaranteed to be not None by while loop condition)
            while p.val == seek.val: # while the seeking pointer points to a duplicate of the current node
                seek = seek.next # keep seeking
                if seek == None: # if the seeking pointer has reached the end of the LL
                    p.next = None # then all nodes after the current node are duplicates, can truncate the LL after the current node
                    return head

            # the seeking node is at the first non-duplicate node (may not have moved at all, if there were no duplicates)
            p.next = seek # skip over all duplicate nodes (if any) by forwarding the next pointer of the current node to the seeked to node
            p = p.next

        return head
Enter fullscreen mode Exit fullscreen mode

We can make it a bit more readable using suggestions from Elements of Programming interviews, and then we get:

    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        first = head

        while first:
            second = first.next
            while second and first.val == second.val:
                second = second.next
            # skip over all duplicate nodes
            first.next = second
            first = first.next

        return head
Enter fullscreen mode Exit fullscreen mode

In the end it's kinda simple.

As usual it's really best to just work out the whole thing on paper, code will just get in the way.

I'm new to the grind, the hardest thing so far is to just stick to it.

Top comments (0)