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

简介: leetcode82. 删除排序链表中的重复元素 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

题目数据保证链表已经按升序 排列

思路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


目录
相关文章
|
1天前
|
存储
力扣 合并两个有序数列||移除元素
力扣 合并两个有序数列||移除元素
6 0
|
2天前
LeetCode链表hard 有思路?但写不出来?
LeetCode链表hard 有思路?但写不出来?
|
2天前
|
Java C语言
剑指offer(牛客)——合并两个排序的链表
剑指offer(牛客)——合并两个排序的链表
8 1
|
2天前
|
索引
每日一题:力扣328. 奇偶链表
每日一题:力扣328. 奇偶链表
13 4
|
2天前
leetcode代码记录(下一个更大元素 II
leetcode代码记录(下一个更大元素 II
8 0
|
2天前
|
索引
leetcode代码记录(下一个更大元素 I
leetcode代码记录(下一个更大元素 I
7 0
|
2天前
leetcode代码记录(移除链表元素
leetcode代码记录(移除链表元素
10 0
|
2天前
leetcode代码记录(移除元素
leetcode代码记录(移除元素
10 0
【每日一题】LeetCode——反转链表
【每日一题】LeetCode——反转链表
【每日一题】LeetCode——链表的中间结点
【每日一题】LeetCode——链表的中间结点