LeetCode 题解工作台
删除排序链表中的重复元素
给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。 示例 1： 输入： head = [1,1,2] 输出： [1,2] 示例 2： 输入： head = [1,1,2,3,3] 输出： [1,2,3] 提示： 链表中节点数目在范围 [0, 3…
1
题型
7
代码语言
3
相关题
当前训练重点
简单 · 链表指针操作
答案摘要
我们用一个指针 来遍历链表。如果当前 与 对应的元素相同，我们就将 的 指针指向 的下下个节点。否则，说明链表中 对应的元素是不重复的，因此可以将 指针移动到下一个节点。 遍历结束后，返回链表的头节点即可。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 链表指针操作 题型思路
题目描述
给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
示例 1：
输入：head = [1,1,2] 输出：[1,2]
示例 2：
输入：head = [1,1,2,3,3] 输出：[1,2,3]
提示：
- 链表中节点数目在范围
[0, 300]内 -100 <= Node.val <= 100- 题目数据保证链表已经按升序 排列
解题思路
方法一：一次遍历
我们用一个指针 来遍历链表。如果当前 与 对应的元素相同，我们就将 的 指针指向 的下下个节点。否则，说明链表中 对应的元素是不重复的，因此可以将 指针移动到下一个节点。
遍历结束后，返回链表的头节点即可。
时间复杂度 ，其中 是链表的长度。空间复杂度 。
# 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]:
cur = head
while cur and cur.next:
if cur.val == cur.next.val:
cur.next = cur.next.next
else:
cur = cur.next
return head
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because each node is visited once. Space complexity is O(1) for iterative solutions and O(n) for recursive calls due to the call stack. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Wants to see clear pointer updates and in-place modifications.
- question_mark
Checks for understanding of linked list traversal and duplicate detection.
- question_mark
May probe handling of empty lists or lists with all identical values.
常见陷阱
外企场景- error
Forgetting to check current.next before accessing its value can cause null pointer errors.
- error
Incorrectly skipping nodes may remove distinct values along with duplicates.
- error
Using extra data structures violates the O(1) space expectation for this problem.
进阶变体
外企场景- arrow_right_alt
Remove duplicates from a sorted doubly linked list.
- arrow_right_alt
Return the count of unique elements while modifying the list in place.
- arrow_right_alt
Allow at most two occurrences of each element instead of one.