LeetCode 题目 82:删除排序链表中的重复元素 II

简介: LeetCode 题目 82:删除排序链表中的重复元素 II

作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。

会一些的技术:数据分析、算法、SQL、大数据相关、python

欢迎加入社区:码上找工作

作者专栏每日更新:

LeetCode解锁1000题: 打怪升级之旅

python数据分析可视化:企业实战案例

python源码解读

备注说明:方便大家阅读,统一使用python,带必要注释,公众号 数据分析螺丝钉 一起打怪升级

题目描述

给定一个已排序的链表的头节点 head,删除原始链表中所有重复数字的节点,只留下不同的数字。返回已排序的链表。

输入格式
  • head:链表的头节点。
输出格式
  • 返回处理后的链表的头节点。

示例

示例 1
输入: 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5
输出: 1 -> 2 -> 5
示例 2
输入: 1 -> 1 -> 1 -> 2 -> 3
输出: 2 -> 3

方法一:哨兵节点 + 双指针

解题步骤
  1. 使用哨兵节点:在链表前添加一个哨兵节点,简化边界条件处理。
  2. 双指针追踪:使用两个指针 prevcurrprev 指向最后一个不重复的节点,curr 用于遍历链表。
完整的规范代码
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
def deleteDuplicates(head):
    """
    使用哨兵节点和双指针删除所有重复的元素
    :param head: ListNode, 链表的头节点
    :return: ListNode, 修改后的链表头节点
    """
    sentinel = ListNode(0)
    sentinel.next = head
    prev = sentinel
    while head:
        # 如果当前节点是重复节点
        if head.next and head.val == head.next.val:
            # 跳过当前节点的所有重复实例
            while head.next and head.val == head.next.val:
                head = head.next
            # 连接 prev 到 head 的下一个节点(跳过所有重复的节点)
            prev.next = head.next
        else:
            # 不重复则移动 prev
            prev = prev.next
        head = head.next
    return sentinel.next
# 示例调用代码
# 创建链表函数及打印函数假定已定义
算法分析
  • 时间复杂度:(O(n)),其中 (n) 是链表的长度。我们需要遍历所有的元素最多两次。
  • 空间复杂度:(O(1)),使用了常数空间额外存储。

方法二:递归法

解题步骤
  1. 递归删除:使用递归函数删除重复的元素,如果当前元素与下一个元素重复,则跳过当前的所有重复元素。
完整的规范代码
def deleteDuplicates(head):
    """
    递归删除所有重复的元素
    :param head: ListNode, 链表的头节点
    :return: ListNode, 修改后的链表头节点
    """
    if not head or not head.next:
        return head
    
    if head.val == head.next.val:
        while head.next and head.val == head.next.val:
            head = head.next
        return deleteDuplicates(head.next)
    else:
        head.next = deleteDuplicates(head.next)
        return head
# 示例调用代码
# 创建链表函数及打印函数假定已定义
算法分析
  • 时间复杂度:(O(n)),递归会访问每个节点一次。
  • 空间复杂度:(O(n)),在最坏的情况下,递归栈的深度可以达到 (n)。

方法三:一次遍历

解题步骤
  1. 直接遍历:只使用一个指针遍历整个链表,根据当前节点和下一节点的值是否相同决定是否删除。
完整的规范代码
def deleteDuplicates(head):
    """
    一次遍历删除所有重复的元素
    :param head: ListNode, 链表的头节点
    :return: ListNode, 修改后的链表头节点
    """
    dummy = ListNode(0)
    dummy.next = head
    current = dummy
    while current.next and current.next.next:
        if current.next.val == current.next.next.val:
            val = current.next.val
            while current.next and current.next.val == val:
                current.next = current.next.next
        else:
            current = current.next
    return dummy.next
# 示例调用代码
# 创建链表函数及打印函数假定已定义
算法分析
  • 时间复杂度:(O(n)),一次遍历链表。
  • 空间复杂度:(O(1)),只使用了有限的额外空间。

方法四:哈希表记录法

解题步骤
  1. 使用哈希表记录频率:首先遍历整个链表,使用哈希表记录每个元素出现的频率。
  2. 根据哈希表重建链表:再次遍历链表,根据哈希表中记录的频率决定是否保留节点。
完整的规范代码
def deleteDuplicates(head):
    """
    使用哈希表记录频率,然后删除所有重复的元素
    :param head: ListNode, 链表的头节点
    :return: ListNode, 修改后的链表头节点
    """
    from collections import Counter
    counter = Counter()
    node = head
    while node:
        counter[node.val] += 1
        node = node.next
    dummy = ListNode(0)
    dummy.next = head
    current = dummy
    while current.next:
        if counter[current.next.val] > 1:
            current.next = current.next.next
        else:
            current = current.next
    return dummy.next
# 示例调用代码
# 创建链表函数及打印函数假定已定义
算法分析
  • 时间复杂度:(O(n)),两次遍历链表,一次建立哈希表,一次重建链表。
  • 空间复杂度:(O(n)),哈希表的大小取决于链表的长度。

方法五:快慢指针法

解题步骤
  1. 快慢指针:快指针用于探测重复元素,慢指针用于连接非重复元素。
完整的规范代码
def deleteDuplicates(head):
    """
    使用快慢指针删除所有重复的元素
    :param head: ListNode, 链表的头节点
    :return: ListNode, 修改后的链表头节点
    """
    dummy = ListNode(0)
    dummy.next = head
    slow = dummy
    while head:
        if head.next and head.val == head.next.val:
            # 跳过当前的重复元素
            while head.next and head.val == head.next.val:
                head = head.next
            slow.next = head.next  # 连接到第一个不重复的元素
        else:
            slow = slow.next  # 不重复,慢指针前进
        head = head.next  # 快指针始终前进
    return dummy.next
# 示例调用代码
# 创建链表函数及打印函数假定已定义
算法分析
  • 时间复杂度:(O(n)),遍历整个链表。
  • 空间复杂度:(O(1)),只使用了有限的额外空间。

不同算法的优劣势对比

特征 方法一:哨兵节点 方法二:递归法 方法三:一次遍历 方法四:哈希表 方法五:快慢指针
时间复杂度 (O(n)) (O(n)) (O(n)) (O(n)) (O(n))
空间复杂度 (O(1)) (O(n)) (O(1)) (O(n)) (O(1))
优势 简单直观,易于实现 自然处理,直观 避免使用额外空间 明确记录每个值的出现次数 避免额外空间,直观有效
劣势 基础方法 栈溢出风险,大量递归 稍微复杂 需要额外空间,复杂度增加 逻辑稍微复杂,需要细致处理

应用示例

去重应用:在需要去除重复数据的多种应用场景中,如邮件列表处理、社交网络服务中的好友推荐等。

数据清洗:在预处理数据时删除重复的数据项,确保数据的质量和分析的准确性。

内存优化:在资源受限的环境中,例如嵌入式系统或移动设备,优化内存使用,提高性能。

这些方法提供了多种处理链表去重的策略,适用于不同的场景和需求,选择合适的方法可以提高代码效率和可读性。


欢迎关注微信公众号 数据分析螺丝钉

相关文章
|
10天前
【数据结构OJ题】移除链表元素
力扣题目——移除链表元素
12 2
【数据结构OJ题】移除链表元素
|
24天前
|
C语言
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
11 1
|
9天前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
1月前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
15天前
链表4(法二)------7-4 sdut-C语言实验-单链表中重复元素的删除
链表4(法二)------7-4 sdut-C语言实验-单链表中重复元素的删除
12 0
|
17天前
2670.找出不同元素数目差数组-力扣(LeetCode)
2670.找出不同元素数目差数组-力扣(LeetCode)
8 0
|
21天前
|
存储 算法 Java
力扣经典150题第四十五题:存在重复元素 II
力扣经典150题第四十五题:存在重复元素 II
11 0
|
24天前
|
算法
【数据结构与算法 刷题系列】移除链表元素
【数据结构与算法 刷题系列】移除链表元素
|
1月前
|
索引
leetcode题解:27.移除元素
leetcode题解:27.移除元素
19 0
|
1月前
|
容器
【LeetCode刷题】栈和队列题目练习~
【LeetCode刷题】栈和队列题目练习~

热门文章

最新文章