当前位置：首页 > news >正文

力扣 83 . 删除排序链表中的重复元素：深入解析与实现

news 2025/6/7 14:04:28

一、链表扫盲专区

1.1 什么是链表？

1.2 单向链表特性

1.3 链表 vs 数组

二、问题分析

2.1 题目要求

2.2 关键点分析

三、算法思路剖析

3.1 双指针法

3.2 流程演示

四、代码深度解析

4.1 关键点解读

4.2 复杂度分析

五、边界条件处理

5.1 特殊输入处理

5.2 常见错误

六、实战测试

一、链表扫盲专区

1.1 什么是链表？

链表是由一系列节点组成的线性数据结构，每个节点包含：

数据域：存储当前节点的值
指针域：指向下一个节点的内存地址

1.2 单向链表特性

非连续存储：节点分散在内存各处
单向访问：只能从头节点开始顺序访问
时间复杂度：
- 查找：O(n)
- 插入/删除：O(1)（已知前驱节点时）

1.3 链表 vs 数组

特性	数组	链表
内存连续性	连续	非连续
随机访问	O(1)	O(n)
插入/删除效率	O(n)	O(1)
空间利用率	固定	动态分配

二、问题分析

2.1 题目要求

给定一个已排序的链表，删除所有重复元素，使每个元素只出现一次。

示例：

输入：1 -> 1 -> 2
输出：1 -> 2

2.2 关键点分析

已排序：重复元素必定相邻
保留一个：发现重复时保留首个元素
原地修改：需直接修改链表结构

三、算法思路剖析

3.1 双指针法

使用当前指针进行遍历：

初始化指针cur指向头节点
循环检查cur与cur.next：
- 值相同 → 删除后一个节点
- 值不同 → 指针前移

3.2 流程演示

当 cur.val 和 cur.next.val 相等时说明需要去重，则将 cur 的下一个指针指向下一个的下一个，这样就能达到去重复的效果

如果不相等则 cur 移动到下一个位置继续循环

当 cur 和 cur.next 的存在为循环结束条件，当二者有一个不存在时说明链表没有去重复的必要了

以链表 1->1->2->3->3 为例：

初始状态：①→①→②→③→③
第1步：发现重复，跳过第二个1 → ①→②→③→③
第2步：1≠2，指针前移
第3步：2≠3，指针前移
第4步：发现重复，跳过第二个3 → ①→②→③

四、代码深度解析

var deleteDuplicates = function(head) {let cur = head;while(cur && cur.next) {if(cur.val === cur.next.val) {cur.next = cur.next.next; // 跳过重复节点} else {cur = cur.next; // 指针前移}}return head;
};

4.1 关键点解读

循环条件：cur && cur.next确保能安全访问两个节点
删除操作：直接修改next指针实现节点跳过
指针移动：仅当无重复时才移动指针

4.2 复杂度分析

时间复杂度：O(n) 只需一次遍历
空间复杂度：O(1) 仅使用常量空间

五、边界条件处理

5.1 特殊输入处理

输入情况	处理方式
空链表	直接返回null
单节点链表	直接返回原链表
全重复链表	保留头节点

5.2 常见错误

空指针异常：未检查cur.next是否存在
尾部处理：最后一个节点的next应为null
指针移动错误：在删除节点后错误移动指针

六、实战测试

// 定义链表节点
class ListNode {constructor(val, next) {this.val = val === undefined ? 0 : val;this.next = next === undefined ? null : next;}
}// 链表去重函数
const deleteDuplicates = function (head) {let cur = head;while (cur && cur.next) {if (cur.val === cur.next.val) {cur.next = cur.next.next;} else {cur = cur.next;}}return head;
};// 数组转链表
function createList(arr) {if (!arr || arr.length === 0) return null;const dummy = new ListNode(-1);let cur = dummy;for (const num of arr) {cur.next = new ListNode(num);cur = cur.next;}return dummy.next;
}// 链表转数组（用于验证结果）
function listToArray(head) {const res = [];while (head) {res.push(head.val);head = head.next;}return res;
}// 测试用例
const testCases = [[1, 1, 2], [1, 1, 1], [], [1, 2, 3, 3, 4]];testCases.forEach((tc) => {const input = createList(tc);const result = deleteDuplicates(input);console.log(`输入：${tc}\t输出：`, listToArray(result));
});