一次遍历
复杂度
-
时间复杂度：
O(N)，对链表每个节点遍历了一次； -
空间复杂度：
O(1)
实现代码
var deleteDuplicates = function(head) {
let dummy = new ListNode(0, head), cur = dummy;
while(cur.next && cur.next.next) {
if (cur.next.val === cur.next.next.val) {
const tmp = cur.next.val;
while(cur.next && cur.next.val === tmp) cur.next = cur.next.next;
}else {
cur = cur.next;
}
}
return dummy.next;
};
哨兵节点 + 双指针
解题思路
初始化哑结点（哨兵节点/虚拟节点）dmy 指向 head ，初始化快慢指针 fast、slow；
fast 指针用来寻找重复的节点，只要 fast 和 fast.next 的值相等，fast 则向后移动；
原本 fast 和 slow 指针只相差一个位置，当出现重复的值 fast 就会向后移动，fast 和 slow 就会相差多个位置，这时
slow.next = fast.next删除重复的值；最后返回结果 dmy.next；
复杂度
-
时间复杂度：
O(N)，对链表每个节点遍历了一次； -
空间复杂度：
O(1)
代码实现
var deleteDuplicates = function (head) {
// 初始化快慢指针 slow、fast，分别指向 dmy、head
let dmy = new ListNode(0, head);
let slow = dmy;
let fast = dmy.next;
while (fast) {
// 若 fast 和下一个节点值相等，fast 向后移动
while (fast.next !== null && fast.val === fast.next.val) fast = fast.next;
// 原本 slow 和 fast 只相差一个位置，只要相差多个位置就说明「出现重复」
slow.next === fast ? slow = slow.next : slow.next = fast.next;
fast = fast.next;
}
return dmy.next
};
递归
复杂度
-
时间复杂度：
O(N)，每个节点访问了一次； -
空间复杂度：
O(N)
代码实现
var deleteDuplicates = function (head) {
// 1. 终止条件：只有一个节点或没有节点 直接返回
if (head == null || head.next == null) return head;
// 2. 递归会有两种情况：
if (head.next.val === head.val) {
// 2-1. 当 head 和 head.next 的值相同，则一直向后查找
while (head.next && head.val === head.next.val) head.next = head.next.next;
// 返回删除重复项后的链表
return deleteDuplicates(head.next);
} else {
// 2-2. head 和 head.next 的值不同，继续向后递归
head.next = deleteDuplicates(head.next);
}
return head;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 83. 删除排序链表中的重复元素
上一篇
评论
