一次遍历
复杂度
-
时间复杂度：
O(n)，其中 n 是链表的长度； -
空间复杂度：
O(1)
实现代码
var deleteDuplicates = function(head) {
if (head === null) return null;
let cur = head;
while (cur.next) {
if (cur.next.val === cur.val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return head;
};
快慢指针
解题思路
初始化 slow 和 fast 两个节点，slow 指向 head ，fast 指向 head.next；
判断 fast 的值是否等于 slow：
- 等于则直接
slow.next = fast.next删除 fast 节点，fast 继续向后移动一个位置；- 不等于则将 slow 向后移动一个位置，fast 继续向后移动一个位置；
直到 fast 走到最后，返回结果 head；
复杂度
-
时间复杂度：
O(n)，其中 n 是链表的长度； -
空间复杂度：
O(1)
代码实现
var deleteDuplicates = function (head) {
if (!head || !head.next) return head;
let slow = head, fast = head.next;
while (fast) {
if (slow.val === fast.val) {
slow.next = fast.next;
}else{
slow = slow.next;
}
fast = fast.next;
}
return head;
};
尾递归
解题思路
deleteDuplicates 递归执行直到链表的最后，从后向前处理；
再判断
head.val === head.next.val相等则删除 head.next 节点；返回结果 head；
复杂度
-
时间复杂度：
O(n) -
空间复杂度：
O(n)
代码实现
var deleteDuplicates = function (head) {
if (head === null || head.next === null) return head;
head.next = deleteDuplicates(head.next);
if (head.val === head.next.val) {
head.next = head.next.next;
}
return head;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
136.只出现一次的数字
上一篇
评论
