作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
题目描述
给定一个排序链表，删除所有含有重复数字的节点，只留下原始链表中 没有重复出现 的数字。
输入格式
- head：链表的头节点。
输出格式
- 返回处理后的链表的头节点。
示例
示例 1
输入: 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5 输出: 1 -> 2 -> 5
示例 2
输入: 1 -> 1 -> 1 -> 2 -> 3 输出: 2 -> 3
解题思路
方法一：哨兵节点 + 双指针
解题步骤
- 使用哨兵节点：在链表前添加一个哨兵节点，简化边界条件处理。
- 双指针追踪：使用两个指针
prev和curr，prev指向最后一个不重复的节点，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.next = head.next else: prev = prev.next head = head.next return sentinel.next # 示例调用 # 创建链表函数及打印函数假定已定义
算法分析
- 时间复杂度：(O(n))，其中 (n) 是链表的长度。我们需要遍历所有的元素最多两次。
- 空间复杂度：(O(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)。
方法三：一次遍历
解题步骤
- 直接遍历：只使用一个指针遍历整个链表，根据当前节点和下一节点的值是否相同决定是否删除。
完整的规范代码
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))，只使用了有限的额外空间。
方法四：哈希表记录法
解题步骤
- 使用哈希表记录频率：首先遍历整个链表，使用哈希表记录每个元素出现的频率。
- 根据哈希表重建链表：再次遍历链表，根据哈希表中记录的频率决定是否保留节点。
完整的规范代码
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))，哈希表的大小取决于链表的长度。
方法五：快慢指针法
解题步骤
- 快慢指针：快指针用于探测重复元素，慢指针用于连接非重复元素。
完整的规范代码
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)) |
| 优势 | 简单直观，易于实现 | 自然处理，直观 | 避免使用额外空间 | 明确记录每个值的出现次数 | 避免额外空间，直观有效 |
| 劣势 | 基础方法 | 栈溢出风险，大量递归 | 稍微复杂 | 需要额外空间，复杂度增加 | 逻辑稍微复杂，需要细致处理 |
应用示例
去重应用：在需要去除重复数据的多种应用场景中，如邮件列表处理、社交网络服务中的好友推荐等。
数据清洗：在预处理数据时删除重复的数据项，确保数据的质量和分析的准确性。
内存优化：在资源受限的环境中，例如嵌入式系统或移动设备，优化内存使用，提高性能。
这些方法提供了多种处理链表去重的策略，适用于不同的场景和需求，选择合适的方法可以提高代码效率和可读性。
欢迎关注微信公众号 数据分析螺丝钉
