Python, accepted recursive solution, explained with comments


  • 0
    W

    Here is my solution. Not very trivial, but quite straightforward. And the runtime was pretty decent unexpectedly.

    ## @param distincts_curr Pointer to the last node in distincts
    ## @param curr Pointer to the current node in original linked list
    ## @return void
    def deleteDuplicate_rec(distincts_curr, curr):
        if curr is None:
            distincts_curr.next = None ## no more distincts in the remaining nodes
            return
        ## when curr is at the last node or it has different val with the next node,
        ## it should be added to the distincts
        if (curr.next is None) or (curr.val != curr.next.val):
            distincts_curr.next = curr
            distincts_curr = curr
            curr = curr.next
            deleteDuplicate_rec(distincts_curr, curr)
        else: 
        ## when curr has the same val with its next, jump till the node with 
        ## different val, or till the None
            val = curr.val
            while (not curr is None) and (curr.val == val):
                curr = curr.next
            deleteDuplicate_rec(distincts_curr, curr)
    
    class Solution(object):
        def deleteDuplicates(self, head):
            ## make an empty header node, which points to the distincts
            fake_head = TreeNode(None)
            fake_curr = fake_head
            deleteDuplicate_rec(fake_curr, head)
            return fake_head.next ## skip the header node

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.