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

问题简述

给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
例如：
    给出的链表为 1→2→3→3→4→4→5, 返回 1→2→5.
    给出的链表为 1→1→1→2→3, 返回 2→3.

删除有序链表中重复的元素-II_牛客题霸_牛客网

思路见代码

• 链表问题的核心是保证 pre、cur、nxt 三个指针的关系正确；

• 此外，使用任何节点的值之前要确保该节点不为空；

Python

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return ListNode类
#
class Solution:
    def deleteDuplicates(self , head: ListNode) -> ListNode:
        # write code here
        
        dummy = ListNode(0)
        dummy.next = head
        
        pre, cur = dummy, head
        while cur:
            nxt = cur.next
            if nxt and cur.val == nxt.val:  # 找到相等值的范围（闭区间）
                while nxt.next and nxt.val == nxt.next.val:
                    nxt = nxt.next
                # 退出循环时，nxt 指向的相同值的最后一个，所以下面要用 nxt.next
                pre.next = cur = nxt.next
            else:
                pre, cur = cur, nxt
        
        return dummy.next