type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给定一个已排序的链表的
head,删除所有重复的元素,使每个元素只出现一次 。示例 1:

示例 2:

提示:
- 链表中节点数目在范围
[0, 300]内
100 <= Node.val <= 100
- 题目数据保证链表已经按升序排列
解法一:递归 + 一次跳过连续重复元素
- 链表已经按升序排列, 相同值必形成连续区间/重复段。
- 从某个头结点
head开始,把重复值的节点收缩到只剩一个”的任务,继续交给相同函数处理(递归)。
- 若当前节点值
head.val == head.next.val,说明重复,需要跳过所有相同值节点,递归从下一个不同值节点开始。
- 若不同,则保留当前节点,并递归处理剩余链表。
复杂度
- 时间:O(n),每节点访问一次。
- 空间:O(n),递归调用栈。
解法二:递归 + 每次只删除下一个相等节点
- 每层递归只去重一对相邻节点。
- 无论相等与否,先递归处理
head.next的去重,再根据当前与head.next的值关系决定是否跳过。
复杂度
- 时间:O(n),每节点访问一次。
- 空间:O(n),递归栈。
解法三:迭代 + 双指针(推荐)
双指针:
prev:指向当前已确认保留的节点(即“去重后链表的末尾”);
cur:扫描指针,试图把它接在prev后面,或把它跳过。
检查
cur 是否能作为新值接到 prev 后。如果
cur.val == prev.val:这是重复值,删除 cur(即跳过),否则更新 prev = cur。复杂度
- 时间:O(n),单次遍历。
- 空间:O(1),原地修改。
解法四:迭代 + 集合去重(通用解法)
- 放弃有序特性,退化到通用做法。
- 扫描链表,用
set记录已出现值:
- 遍历链表时,若下一个节点值已在集合中,则删除;否则加入集合。
复杂度
- 时间:O(n),遍历一次。
- 空间:O(n),存储集合。
- Author:Fan Luo
- URL:https://fanluo.me/article/leetcode-83-删除排序链表中的重复元素
- Copyright:All articles in this blog adopt BY-NC-SA agreement. Please indicate the source!
上一篇
[Leetcode 79] 单词搜索
下一篇
[Leetcode 84] 柱状图中最大的矩形