0083.删除排序链表中的重复元素
难度：🟢 简单
标签：链表
题目描述
给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
示例 1：
输入：head = [1,1,2]
输出：[1,2]
示例 2：
输入：head = [1,1,2,3,3]
输出：[1,2,3]
解题思路
核心思想
本题的核心是利用链表 已排序 的特性。这意味着所有重复的元素必然是相邻的。因此，我们只需要遍历整个链表，比较当前节点和它的下一个节点的值即可。
思路选择
单指针迭代法 是解决此问题最简洁、最高效的思路。我们只需要一个指针 current 从头节点开始遍历。
如果
current的值与current.next的值相同，说明遇到了重复元素。我们就“跳过”下一个节点，即current.next = current.next.next。如果值不相同，说明
current.next是一个不重复的元素，我们正常地将current指针后移一位即可。
关键步骤
处理边界情况：如果链表为空 (
head === null)，直接返回null。初始化指针：创建一个指针
current，指向头节点head。循环遍历：当
current和current.next都不为空时，持续循环。 a. 判断重复: 比较current.val和current.next.val。 b. 删除重复: 如果值相等，通过current.next = current.next.next来删除重复的后一个节点。注意，此时current指针 不移动，因为它需要继续和新的current.next进行比较，以处理连续多个重复元素的情况（例如1->1->1）。 c. 移动指针: 如果值不相等，说明当前节点和下一个节点不重复，将current移动到下一个位置current = current.next。返回结果：循环结束后，链表中已无重复元素，返回原始的
head。
代码实现 (推荐)
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var deleteDuplicates = function (head) {
if (head === null) {
return null;
}
let current = head;
while (current !== null && current.next !== null) {
if (current.val === current.next.val) {
// 跳过重复的节点
current.next = current.next.next;
} else {
// 移动到下一个不同的节点
current = current.next;
}
}
return head;
};
原始代码分析 (用户提供)
您提供的代码使用了两个指针 prev 和 cur，逻辑上是可行的，但可以被简化。
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var deleteDuplicates = function (head) {
// 处理边界情况
if (head === null || head.next === null) return head;
// prev 指向结果链表的最后一个节点，cur 用于遍历
let prev = head, cur = head.next, dummy = head;
while (cur !== null) {
// 如果遇到重复节点，仅移动 cur 指针
if (prev.val === cur.val) {
cur = cur.next;
continue;
}
// 如果不重复，将 prev 的 next 指向 cur，并移动两个指针
prev.next = cur;
prev = prev.next;
cur = cur.next;
}
// 关键：处理链表末尾是重复元素的情况，例如 [1, 2, 2, 2]
prev.next = null;
return dummy;
};
优点：逻辑可以正确处理所有情况。
待改进：
使用了两个指针
prev和cur，比单指针法稍显复杂。在没有重复的情况下，
prev.next = cur和prev = prev.next这两步是冗余的，因为它们本身就相等。最后需要手动设置
prev.next = null来断开与末尾重复元素的连接，增加了额外的处理步骤。
复杂度分析
时间复杂度：O(n) 其中 n 是链表的长度。我们只需要对链表进行一次完整的遍历。
空间复杂度：O(1) 我们只使用了常数个额外变量作为指针，空间消耗是恒定的。
相关题目
总结
本题是链表操作的入门题，旨在考察对指针操作的基本功。利用“已排序”这一关键信息，可以大大简化问题。推荐的单指针法更为简洁和优雅，是解决此问题的标准范式。