Remove Duplicates from Sorted List II

Question

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example, Given 1->2->3->3->4->4->5, return 1->2->5. Given 1->1->1->2->3, return 2->3.

Tags

• Linked List

Thought

The problem is similar to the problem Remove Duplicates from Sorted List. However, it requires to remove all the unnecessary nodes.

Code

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None:
            return head
        dummy = ListNode(-1)
        parentNode = dummy
        prev = None
        current = head
        next = current.next
        while next:
            if (prev is None and current.val != next.val) or (prev is not None and prev.val != current.val != next.val):
                parentNode.next = current
                parentNode = parentNode.next
            prev = current
            current = next
            next = current.next
        if prev is None or current.val != prev.val:
            parentNode.next = current
            parentNode = parentNode.next
        parentNode.next = None
        return dummy.next