题解 | 删除有序链表中重复的元素-II -O(1) 看官方题解

# class ListNode:


#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return ListNode类
#
class Solution:
    """
    测试样例： {1,1,1}  预期结果：{}
    解题思路： 1.使用两个数组 其中一个作为记录结果arr ，一个作为记录重复元素temp
    2.最后arr中删除 temp 中出现的 重复元素
    3. 定义一个newhead 拼接 arr 的元素为链表
    """
    def deleteDuplicates2(self , head: ListNode) -> ListNode:
        arr=[]
        temp=[]
        if not head:
            return head
        cur =head
        while cur:
            if cur.val not in arr:
                arr.append(cur.val)
            else:
                 if cur.val not in temp:  # temp 中不能有重复
                    temp.append(cur.val)
            cur=cur.next
        for  i in temp:  # 删除重复出现的
            
            arr.remove(i)
             
        newHead=ListNode(-1)
        cur =newHead
        for  i in arr:
            cur.next=ListNode(i)
            cur =cur.next
        return  newHead.next


    """
    解题思路：牛客官方题解 
    升序链表特点：相同的元素都连续
    比较到重复的元素，循环删除连续的节点，连接到第一个不相同的节点
    添加 虚拟头结点 ，可能出现删除头结点
    关键代码段：
     cur=pre #cur =head  应该指向虚拟头结点 否则删除不掉第一个节点
        while  cur.next and  cur.next.next:# 关键点
            if cur.next.val==cur.next.next.val: # 出现重复 进入删除操作
                temp =cur.next.val # 记录当前重复值用于循环比较
                while cur.next and cur.next.val==temp:
                    cur.next=cur.next.next 
            else:
                cur=cur.next 
    if cur.
    测试样例： {1,1,1}  预期结果：{}  

    """
    def deleteDuplicates(self , head: ListNode) -> ListNode:
        # write code here
        if  not head :
            return None
       
        pre =ListNode(-1)  # 虚拟头结点
        pre.next=head
        cur=pre #cur =head  应该指向虚拟头结点 否则删除不掉第一个节点
        while  cur.next and  cur.next.next:# 关键点
            if cur.next.val==cur.next.next.val: # 出现重复 进入删除操作
                temp =cur.next.val # 记录当前重复值用于循环比较
                while cur.next and cur.next.val==temp:
                    cur.next=cur.next.next 
            else:
                cur=cur.next
        return pre.next