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

发布时间:2024年01月15日

题目

给定一个已排序的链表的头 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
题目数据保证链表已经按升序 排列

思路1

遍历两次,第一次遍历的时候声明一个set集合,存储所有出现过多次的节点,在第二次遍历的时候使用双指针,cur指针在前,pre指针在后,如果发现cur指向的节点在集合中,则将cur向后移动,否则移动pre和cur节点
最终返回事先声明的dom节点,因为head节点指向的值可能多次出现,这里我们不可以直接返回head

复杂度

时间复杂度:

遍历了两次, O ( 2 n ) O(2n) O(2n)

空间复杂度:

存储了出现两次的节点, O ( n ) O(n) O(n)

Code2

# 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: Optional[ListNode]) -> Optional[ListNode]:
        s = set()
        if not head: return head
        pre,cur = ListNode(),head
        dom = pre
        while  cur.next:
            if cur.val == cur.next.val:
                s.add(cur.val)
            cur = cur.next

        cur = head
        while cur:
            while cur and cur.val in s:    
                cur = cur.next
            
            pre.next = cur
            
            if not cur: break
            cur = cur.next
            pre = pre.next

        return dom.next

思路2

只声明一个指针cur,在while循环中判断cur.next和cur.next,next是否存在。如果这两个值不等,说明cur.next是不重复出现的,可以当作cur的下一个节点;
否则说明这两个数一样,则这两个数需要去除,我们这里进一个while循环,不断推进cur.next的值,知道cur.next的值得不是最开始出现的那两个相同的数,如果他是none,则此时cur.next就是none,不需要额外操作,如果他是一个数字,且后面还有节点,则继续循环

复杂度2

时间复杂度:

遍历一次: O ( n ) O(n) O(n)

空间复杂度:

没有声明额外空间: O ( 1 ) O(1) O(1)

Code2

# 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: Optional[ListNode]) -> Optional[ListNode]:
        cur = dumy = ListNode(next=head)
        while cur.next and cur.next.next:
            val = cur.next.val
            if val == cur.next.next.val:
                while cur.next and cur.next.val == val:
                    cur.next = cur.next.next
            else:
                cur = cur.next
        return dumy.next
文章来源:https://blog.csdn.net/qq_51118755/article/details/135600863
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。