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

简介: leetcode83. 删除排序链表中的重复元素

题目

给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。

示例 1:

输入:head = [1,1,2] 输出:[1,2] 示例 2:

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

提示:

链表中节点数目在范围 [0, 300] 内

-100 <= Node.val <= 100 题目数据保证链表已经按升序 排列

思路1

模拟题目中的要求,遍历整个链表,如果当前节点和下一个节点数值相同,则删除下一个节点,,注意要事先保存头节点,最后返回头节点即可

复杂度

时间复杂度:

我们只遍历一遍链表,第二个while循环删除节点,并不是遍历 O ( n ) O(n)O(n)

空间复杂度:

用到了常数级空间 O ( 1 ) O(1)O(1)

Code

# 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]:
        node = head
        while head and head.next:
            while head.next and head.val == head.next.val:
                head.next = head.next.next
            head = head.next
        return node

思路2

使用快慢指针,快指针遍历所有节点,如果快指针的值和慢指针不同,说明找到了不同的节点,然后将slow节点后面的节点赋值fast即可

我们最后一次赋值的时候,如果此时的fast节点后面仍然有值,则slow后面也会带着,所以最后要切断slow后面的节点

复杂度

时间复杂度:

依旧只遍历一遍链表 O ( n ) O(n)O(n)

空间复杂度:

O ( 1 ) O(1)O(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: Optional[ListNode]) -> Optional[ListNode]:
        if not head:return head
        fast,slow = head,head
        while fast:
            if slow.val != fast.val:
                slow.next = fast
                slow = slow.next
            fast = fast.next
        slow.next = None
        return head


目录
相关文章
|
1天前
题目----力扣--回文链表
题目----力扣--回文链表
5 0
|
1天前
题目----力扣--移除链表元素
题目----力扣--移除链表元素
6 1
|
2天前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
10 1
|
2天前
|
索引
【力扣刷题】删除链表的倒数第 N 个结点、两两交换链表中的节点、随机链表的复制
【力扣刷题】删除链表的倒数第 N 个结点、两两交换链表中的节点、随机链表的复制
8 0
|
2天前
|
存储 算法 索引
【力扣刷题】只出现一次的数字、多数元素、环形链表 II、两数相加
【力扣刷题】只出现一次的数字、多数元素、环形链表 II、两数相加
12 1
|
2天前
|
索引
【力扣刷题】回文链表、环形链表、合并两个有序链表
【力扣刷题】回文链表、环形链表、合并两个有序链表
9 0
|
2天前
|
索引
【力扣刷题】两数求和、移动零、相交链表、反转链表
【力扣刷题】两数求和、移动零、相交链表、反转链表
11 2
【力扣刷题】两数求和、移动零、相交链表、反转链表
|
7天前
|
算法 索引
【数据结构与算法 | 基础篇】[链表专题]力扣141, 142
【数据结构与算法 | 基础篇】[链表专题]力扣141, 142
|
2天前
|
算法
"刷题记录:哈希表+双指针 | leetcode-2465. 不同的平均值数目 "
该文段是一篇关于编程题目的解答,主要讨论如何找到数组中所有不同平均值的个数。作者首先使用排序和哈希集来解决,将数组转为列表排序后,通过双指针计算平均值并存入哈希集以去重。然后,作者发现可以优化方案,通过双指针在排序后的数组中直接计算两数之和,用哈希集记录不重复的和,从而避免实际计算平均值,提高了算法效率。最终代码展示了这两种方法。
10 0
|
2天前
【力扣刷题】二叉树的中序遍历、二叉树的最大深度、翻转二叉树、对称二叉树
【力扣刷题】二叉树的中序遍历、二叉树的最大深度、翻转二叉树、对称二叉树
7 0