删除链表中重复的节点
题目 删除链表中重复的节点
思路分析
- 通过虚拟头节点简化边界条件处理。
- 使用
head和start指针遍历原链表，跳过重复节点，保留不重复的节点。
代码实现
class Solution {
public ListNode deleteDuplication(ListNode head) {
ListNode dummy = new ListNode(-1); // 创建一个虚拟头节点，值为 -1
dummy.next = head; // 虚拟头节点指向原链表的头节点
ListNode p = dummy; // `p` 用来遍历链表，从虚拟头节点开始
while (p.next != null) { // 当 `p` 的下一个节点存在时
ListNode q = p.next; // `q` 指向 `p` 的下一个节点
// 遍历链表，寻找与 `p.next` 相同值的节点
while (q != null && q.val == p.next.val) q = q.next;
// 如果 `p.next` 到 `q` 之间的节点不止一个，说明有重复节点
if (p.next.next != q) p.next = q; // 将 `p` 的下一个节点直接指向 `q`，跳过所有重复节点
else p = p.next; // 否则，`p` 继续向前移动
}
return dummy.next; // 返回去掉重复节点后的链表头节点
}
}
class Solution {
public ListNode deleteDuplication(ListNode head) {
// 创建一个虚拟头节点，其值为 -1。使用虚拟头节点的目的是便于处理头节点本身是重复节点的情况
ListNode dom = new ListNode(-1);
// 使用一个指针 `start`，指向虚拟头节点。`start` 用来追踪新的链表的最后一个节点
ListNode start = dom;
// 遍历整个链表，直到 `head` 为空
while (head != null) {
// 如果当前节点的下一个节点为空（即当前节点是最后一个节点），或者当前节点的值不等于下一个节点的值
// 说明当前节点不是重复节点
if (head.next == null || head.val != head.next.val) {
// 将当前节点加入到新的链表中
start.next = head;
// 移动 `start` 指针到当前节点，表示新的链表已经包含了该节点
start = head;
}
// 跳过所有与当前节点 `head` 值相同的节点，直到遇到一个不同值的节点或者链表结束
while (head.next != null && head.val == head.next.val) {
head = head.next;
}
// 移动 `head` 指针到下一个节点
head = head.next;
}
// 处理结束，将 `start.next` 置为空，以确保新链表的末尾没有残留的节点
start.next = null;
// 返回新的链表的头节点，即虚拟头节点的下一个节点
return dom.next;
}
}
💬 评论