删除排序链表中的重复元素 II
# 📃 题目描述
题目链接:82. 删除排序链表中的重复元素 II - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。
示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:
输入: 1->1->1->2->3
输出: 2->3
# 🔔 解题思路
使用两个指针,一个指针指向某段重复元素的前驱节点,另一个指针用来扫描重复元素。当遇到重复出现的节点时,直接遍历到该重复节点的末尾,然后删除两个指针中间这一段重复节点。
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 添加一个头节点,方便处理
ListNode dummy = new ListNode(0);
dummy.next = head;
// 指向重复元素的前驱节点
ListNode pre = dummy;
// 扫描重复元素
ListNode cur = head;
while (cur != null) {
// 遇到重复出现的节点
if (cur.next != null && cur.val == cur.next.val) {
// 循环遍历到该重复节点的末尾
while (cur != null && cur.next != null && cur.val == cur.next.val) {
cur = cur.next;
}
// 删除中间这一段重复节点
cur = cur.next;
pre.next = cur;
// 删完这段重复元素后不能更新 pre,因为很有可能现在的 cur.next 又是一段重复元素
// 比如 1 3 3 4 4, pre = 1, 删完 3 后,cur.next = 4,如果更新 pre 为 cur.next = 4 的话,显然是不合题意的(重复元素需要全部删除)
}
else {
pre = cur;
cur = pre.next;
}
}
return dummy.next;
}
}
# 💥 复杂度分析
- 空间复杂度:O(1)
- 时间复杂度:O(N)
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10