删除排序链表中的重复元素(虚拟头结点技巧)|Java 刷题打卡

简介: 删除排序链表中的重复元素(虚拟头结点技巧)|Java 刷题打卡

网络异常,图片无法展示
|


题目描述



这是 LeetCode 上的 83. 删除排序链表中的重复元素


Tag : 「链表」


存在一个按升序排列的链表,给你这个链表的头节点 head ,请你删除所有重复的元素,使每个元素 只出现一次 。


返回同样按升序排列的结果链表。



示例 1:

网络异常,图片无法展示
|


输入:head = [1,1,2]
输出:[1,2]
复制代码


示例 2:

网络异常,图片无法展示
|


输入:head = [1,1,2,3,3]
输出:[1,2,3]
复制代码


提示:


  • 链表中节点数目在范围 [0, 300] 内
  • -100 <= Node.val <= 100
  • 题目数据保证链表已经按升序排列


基本思路



还是与 82. 删除排序链表中的重复元素 II 相似的解题:


  1. 建一个「虚拟头节点」dummy 以减少边界判断,往后的答案链表会接在 dummy 后面
  2. 使用 tail 代表当前有效链表的结尾
  3. 通过原输入的 head 指针进行链表扫描


代码:


class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return head;
        ListNode dummy = new ListNode(-109);
        ListNode tail = dummy;
        while (head != null) {
            // 值不相等才追加,确保了相同的节点只有第一个会被添加到答案
            if (tail.val != head.val) {
                tail.next = head;
                tail = tail.next;
            }
            head = head.next;
        }
        tail.next = null;
        return dummy.next;
    }   
}
复制代码


  • 时间复杂度:O(n)O(n)
  • 空间复杂度:O(1)O(1)


拓展



  • 「重复元素全部删除」,该如何实现?


82. 删除排序链表中的重复元素 II


class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        while (head != null) {
            // 进入循环时,确保了 head 不会与上一节点相同
            if (head.next == null || head.val != head.next.val) {
                tail.next = head;
                tail = tail.next;
            }
            // 如果 head 与下一节点相同,跳过相同节点
            while (head.next != null && head.val == head.next.val) head = head.next;
            head = head.next;
        }
        tail.next = null;
        return dummy.next;
    }
}
复制代码


最后



这是我们「刷穿 LeetCode」系列文章的第 No.83 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
12月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
128 1
|
3月前
|
监控 Java API
Java语言按文件创建日期排序及获取最新文件的技术
这段代码实现了文件创建时间的读取、文件列表的获取与排序以及获取最新文件的需求。它具备良好的效率和可读性,对于绝大多数处理文件属性相关的需求来说足够健壮。在实际应用中,根据具体情况,可能还需要进一步处理如访问权限不足、文件系统不支持某些属性等边界情况。
208 14
|
4月前
|
存储
203. 移除链表元素,707.设计链表,206. 反转链表
链表是数据结构中的重要概念,包含单链表、双链表和循环链表。单链表每个节点存储数据与下一节点指针;双链表增加上一节点指针;循环链表首尾相连。 **例题解析:** 1. **203. 移除链表元素**:通过遍历链表删除指定值节点,注意处理头节点特殊情况。 2. **707. 设计链表**:实现链表的增删查操作,需理解指针操作逻辑,避免直接修改目标节点。 3. **206. 反转链表**:采用双指针或递归方法改变节点指向,完成链表反转。 以上题目涵盖链表核心操作,掌握后可灵活应对相关问题。
|
9月前
|
Java 程序员
Java 排序神器:Comparable 和 Comparator 该怎么选?
嗨,大家好,我是小米!今天和大家聊一聊Java社招面试中常考的经典问题——Comparable和Comparator的区别。Comparable定义对象的自然排序,适用于单一固定的排序规则;Comparator则是策略接口,用于定义自定义排序规则,适用于多样化或多变的排序需求。掌握这两者的区别是理解Java排序机制的基础,也是面试中的加分题。结合实际项目场景深入探讨它们的应用,能更好地打动面试官。如果你觉得有帮助,欢迎点赞、收藏、分享,期待你的一键三连!我们下期见~ 我是小米,一个喜欢分享技术的程序员,关注我的微信公众号“软件求生”,获取更多技术干货!
113 20
|
12月前
|
存储 搜索推荐 算法
【用Java学习数据结构系列】七大排序要悄咪咪的学(直接插入,希尔,归并,选择,堆排,冒泡,快排)以及计数排序(非比较排序)
【用Java学习数据结构系列】七大排序要悄咪咪的学(直接插入,希尔,归并,选择,堆排,冒泡,快排)以及计数排序(非比较排序)
115 1
|
12月前
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
130 0
|
12月前
|
算法
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
125 0
|
12月前
【LeetCode 06】203.移除链表元素
【LeetCode 06】203.移除链表元素
85 0

热门文章

最新文章