LeetCode 83简单链表 · 删除
删除排序链表重复元素 图解题解
这道题到底在问什么
给定升序链表，删除重复节点，使每个元素只出现一次。
- head
- 1→1→2→3→3
- 输出
- 1→2→3
最优解：一步一步想明白
- 3如果链表无序，set 有用。但这里已排序，重复值一定相邻。
- 4cur 指向当前保留节点。若下一个值相同，就跳过下一个；否则 cur 前进。
- 5compare比较 cur 和 cur.next。它们都是 1，发现重复。
- 6skip把 cur.next 指向下下个节点，第二个 1 被链表绕过去。
- 7stay删除后 cur 不前进，因为后面可能还有更多重复值。
- 8move当前值 1 和下一个 2 不同，cur 前进到 2。
- 9skip走到 3 时，再次发现相邻重复，跳过后一个 3。
- 10donecur.next 为空，扫描结束，链表变成 1→2→3。
- 13相等就跳，不等才走。
- 16stay1→1→1 删除第二个 1 后，cur 还要继续和新的 next 比较，不能前进。
- 23这题学完不要乱跳，下一步去 对应专题 连刷同类题；卡住时用 AI 答疑追问“为什么这一步成立”，比只背答案更稳。
⚠️ 容易写错的地方
✗ 错：删除后 cur 立刻前进
✓ 对：删除后 cur 留在原地
可能有 1→1→1 这种连续重复。
✗ 错：while cur.next 不判 cur
✓ 对：while cur and cur.next
空链表会报错。
✗ 错：以为需要 dummy
✓ 对：本题保留第一个节点，cur 即可
不会删除头节点本身。
完整代码（Python / C++ / Java）
Python
class Solution:
def deleteDuplicates(self, head):
cur = head
while cur and cur.next:
if cur.val == cur.next.val:
cur.next = cur.next.next
else:
cur = cur.next
return headC++
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* cur = head;
while (cur && cur->next) {
if (cur->val == cur->next->val) cur->next = cur->next->next;
else cur = cur->next;
}
return head;
}
};Java
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode cur = head;
while (cur != null && cur.next != null) {
if (cur.val == cur.next.val) cur.next = cur.next.next;
else cur = cur.next;
}
return head;
}
}套路模板 · 删除排序链表中的重复元素迁移骨架
# 链表题先固定三件事：dummy、当前指针、下一跳
dummy = ListNode(0)
tail = dummy
while 还有节点要处理:
nxt = 当前节点.next # 改指针前先存后继
tail.next = 选中的节点 # 只改一根箭头
tail = tail.next # tail 必须跟着走
当前指针 = nxt
return dummy.nextListNode dummy(0);
ListNode* tail = &dummy;
while (还有节点要处理) {
ListNode* nxt = cur->next; // 改指针前先存
tail->next = cur; // 接上选中的节点
tail = tail->next; // tail 前进
cur = nxt;
}
return dummy.next;ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (还有节点要处理) {
ListNode nxt = cur.next; // 改指针前先存
tail.next = cur; // 接上选中的节点
tail = tail.next; // tail 前进
cur = nxt;
}
return dummy.next;复杂度
时间复杂度
O(n)
每个节点最多被检查一次
空间复杂度
O(1)
只用 cur 指针
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 删除排序链表重复元素 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
如果要删除所有重复值，一个都不保留呢？+
那是 LC82，需要 dummy，因为头节点可能被删除。
这道题为什么用「删除」，换最直接的暴力解会差在哪？+
删除抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。