删除排序链表中的重复元素 II

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。

返回同样按升序排列的结果链表。

示例 1：

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

示例 2：

输入：head = [1,1,1,2,3]
输出：[2,3]

提示：

• 链表中节点数目在范围 [0, 300] 内
• -100 <= Node.val <= 100
• 题目数据保证链表已经按升序排列

Python 解答：
1.两次扫描

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        adic = {}
        p = head
        while p:
            if p.val not in adic.keys():
                adic[p.val] = 1
            else:
                adic[p.val] += 1
            p = p.next
        guard = ListNode()
        guard.next = head
        cur = guard.next
        pre = guard
        while cur:
            if adic[cur.val] > 1:
                cur = cur.next
                pre.next = cur
            else:
                pre = pre.next
                cur= cur.next
        return guard.next

2。一次扫描

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        #保留单个
        # guard = ListNode(-101)
        # guard.next = head
        # p1, p2 = guard, head
        # while p2:
        #     if p1.val != p2.val:
        #         p1.next = p2
        #         p1 = p1.next
        #         p2 = p2.next
        #     else:
        #         p2 = p2.next
        # return guard.next
        #不保留
        guard = ListNode(-101)
        guard.next = head
        p1, p2 = guard, head
        while p2:
            p3 = p2.next
            if p3 and p2.val == p3.val:
                while p3 and p2.val == p3.val:
                    p2 = p2.next
                    p3 = p3.next
                p1.next = p3
                p2 = p3
            else:
                p1 = p1.next
                p2 = p2.next

        return guard.next