[Leetcode 83] 删除排序链表中的重复元素

type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给定一个已排序的链表的head,删除所有重复的元素,使每个元素只出现一次 。
 
示例 1:
notion image
示例 2:
notion image
提示:
  • 链表中节点数目在范围 [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),存储集合。
上一篇
[Leetcode 79] 单词搜索
下一篇
[Leetcode 84] 柱状图中最大的矩形