app界面设计流程图_站长工具平台_2021年热门关键词_最近的国际新闻

原题地址：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]

解题思路

1. 问题概述：

   • 给定一个排序链表，删除所有含有重复数字的节点，只留下原始链表中没有重复的元素。

2. 问题分析：

   • 这是一个典型的链表问题，要求删除重复元素，特别是当元素有重复时，所有重复的元素都需要被删除，保留一个唯一的元素。
   • 注意到链表是排序的，因此重复的元素总是出现在相邻的位置。

3. 解题思路：

   • 设立一个虚拟头节点 dummy，这样可以避免处理头节点的特殊情况。
   • 使用 cur 指针来遍历链表。
   • 当发现当前节点与下一个节点值相等时，说明有重复元素，应该将这些重复节点全部删除。
   • 否则，移动 cur 指针到下一个节点。
   • 最终返回 dummy.next，即去掉虚拟头节点后的链表。

4. 具体步骤：

   • 通过 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;}
}

复杂度分析

1. 时间复杂度：

   • 链表最多遍历一遍，因此时间复杂度为 O(n)，其中 n 是链表的节点数。

2. 空间复杂度：

   • 我们只用了常数空间来存储 dummy 和 cur，因此空间复杂度为 O(1)。