2024-1-15
文章目录
- [82. 删除排序链表中的重复元素 II](https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/)
82. 删除排序链表中的重复元素 II
思路:
- 创建一个虚拟节点
dummy
作为头节点的前置节点。 - 使用两个指针
pre
和cur
分别指向前一个非重复元素和当前节点。 - 遍历链表,当cur不为空时执行以下操作:
- 如果
cur
和cur
的下一个节点的值相等,则一直向后遍历找到下一个不相等的节点。 - 如果
pre
的下一个节点就是cur
,说明当前节点没有重复,将pre
移动到cur
的位置。 - 如果
pre
的下一个节点不是cur
,说明当前节点有重复,将pre
的next
指针指向cur
的下一个节点,实现删除操作。
- 如果
- 继续遍历下一个节点,直到遍历完整个链表。
- 返回虚拟节点的下一个节点,即为去重后的链表
public ListNode deleteDuplicates2(ListNode head) {
// 创建一个虚拟节点作为头节点的前置节点,方便处理头节点的删除情况
ListNode dummy = new ListNode(0, head);
// pre 节点用于记录上一个非重复元素的位置
ListNode pre = dummy;
// cur 节点用于遍历链表
ListNode cur = head;
// 遍历链表
while (cur != null) {
// 如果当前节点和下一个节点的值相等,则一直向后遍历找到下一个不相等的节点
while (cur.next != null && cur.next.val == cur.val) {
cur = cur.next;
}
// 如果 pre 的下一个节点就是 cur,说明当前节点没有重复,pre 移动到 cur 的位置
if (pre.next == cur) {
pre = cur;
} else {
// 如果 pre 的下一个节点不是 cur,说明当前节点有重复,将 pre 的 next 指针指向 cur 的下一个节点,实现删除操作
pre.next = cur.next;
}
// 继续遍历下一个节点
cur = cur.next;
}
// 返回虚拟节点的下一个节点,即为去重后的链表
return dummy.next;
}
点击移步博客主页,欢迎光临~