Remove Duplicates from Sorted Linked List II

Question

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

Example Given 1->2->3->3->4->4->5, return 1->2->5. Given 1->1->1->2->3, return 2->3.

Thoughts

与上题不同，这一题要求删除所有重复节点，所以head也有可能被删除 一个处理head节点不确定的方法 引入dummy node, dummy.next = head,从dummy开始处理

1. 此题需要将值相等的节点全部删掉，而删除链表的操作与节点前后两个节点都有关系，故需要涉及三个链表节点。且删除单向链表节点时不能删除当前节点，只能改变当前节点的next指向的节点。
2. 在判断val是否相等时需先确定node->next和node->next->next均不为空，否则不可对其进行取值。

Solution

"""
Definition of ListNode
class ListNode(object):

    def __init__(self, val, next=None):
        self.val = val
        self.next = next
"""
class Solution:
    """
    @param head: A ListNode
    @return: A ListNode
    """
    def deleteDuplicates(self, head):
        # write your code here
        if not head:
            return None
        dummy = ListNode(0)
        dummy.next = head
        d = dummy
        while d.next and d.next.next:
            if d.next.val == d.next.next.val:
                valPrev = d.next.val
                #keep deleting until not equal
                while d.next and d.next.val == valPrev:
                    d.next = d.next.next
            else:
                d = d.next
        return dummy.next