当前位置：首页 > article >正文

leetcode82:删除链表中的重复元素II

article 2024/12/28 11:29:50

原题地址：82. 删除排序链表中的重复元素 II - 力扣（LeetCode）

题目描述

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

示例 1：

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

示例 2：

输入：head = [1,1,1,2,3]
输出：[2,3]

解题思路

问题概述：
- 给定一个排序链表，删除所有含有重复数字的节点，只留下原始链表中没有重复的元素。
问题分析：
- 这是一个典型的链表问题，要求删除重复元素，特别是当元素有重复时，所有重复的元素都需要被删除，保留一个唯一的元素。
- 注意到链表是排序的，因此重复的元素总是出现在相邻的位置。
解题思路：
- 设立一个虚拟头节点 dummy，这样可以避免处理头节点的特殊情况。
- 使用 cur 指针来遍历链表。
- 当发现当前节点与下一个节点值相等时，说明有重复元素，应该将这些重复节点全部删除。
- 否则，移动 cur 指针到下一个节点。
- 最终返回 dummy.next，即去掉虚拟头节点后的链表。
具体步骤：
- 通过 dummy 节点指向链表的头部，这样就可以避免一些特殊情况（比如删除头节点时需要特别处理）。
- 遍历链表，若当前节点与下一个节点值相同，说明是重复节点，跳过所有相同的节点。
- 如果当前节点与下一个节点不同，则将 cur 指向下一个节点，继续遍历。

源码实现

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        // 如果链表为空，直接返回空链表
        if (head == null) {
            return head;
        }
        
        // 设置虚拟头节点，方便删除操作
        ListNode dummy = new ListNode(0, head);

        // cur 指针初始化为虚拟头节点
        ListNode cur = dummy;

        // 遍历链表
        while (cur.next != null && cur.next.next != null) {
            // 如果当前节点与下一个节点的值相同，说明有重复节点
            if (cur.next.val == cur.next.next.val) {
                int x = cur.next.val;  // 记录重复的值
                // 跳过所有值等于 x 的节点
                while (cur.next != null && cur.next.val == x) {
                    cur.next = cur.next.next;  // 删除当前节点
                }
            } else {
                // 否则，正常移动 cur 指针
                cur = cur.next;
            }
        }

        // 返回去掉虚拟头节点后的链表
        return dummy.next;
    }
}