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月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
34 1
|
1月前
Leetcode第21题(合并两个有序链表)
这篇文章介绍了如何使用非递归和递归方法解决LeetCode第21题,即合并两个有序链表的问题。
48 0
Leetcode第21题(合并两个有序链表)
|
1月前
【LeetCode 27】347.前k个高频元素
【LeetCode 27】347.前k个高频元素
32 0
|
1月前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
17 0
LeetCode第二十四题(两两交换链表中的节点)
|
1月前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
40 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
1月前
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
46 0
|
1月前
|
算法
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
30 0
|
1月前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
77 0
|
5月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
5月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表