题目描述

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

样例

输入: 1->2->3->3->4->4->5
输出: 1->2->5

算法1

(线性扫描) $O(n)$

1.构建虚拟头dummy
2.从前往后扫描：
1）找是否相同
2）找相同的有几个（区间:双指针）
注：是把重复了的都去除

时间复杂度

参考文献

python 代码

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


def deleteDuplicates( head):
    #构建虚拟头
    dummy = ListNode(-1)
    dummy.next = head
    a = dummy
    b = head
    while b and b.next:
        #难点1.理解是a.next和b.next的值
        if a.next.val != b.next.val:
            a = a.next
            b = b.next
        else:
            #难点2.while结束条件是a.next和b.next值不等
            while b and b.next and a.next.val == b.next.val:
                b = b.next
            a.next = b.next
            b = b.next
    return dummy.next


# 写一个测试用例
if __name__ == "__main__":

    nums = [1, 2, 2, 5, 6, 7, 8, 8, 9]

    #遍历链表
    for i in range(len(nums)):
        if i ==0:
            tmp = ListNode(nums[i])
            head = tmp
        else:
            node = ListNode(nums[i])
            #难点3.构建链表node
            tmp.next = node
            tmp = node

    l2 = deleteDuplicates(head)
    while l2:
        print(l2.val,end=" ")
        l2 = l2.next