LeetCode082

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

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

一、描述

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

示例 1

在这里插入图片描述

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

示例 2
在这里插入图片描述

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

提示

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

二、题解

方法一双指针

使用双指针的方式定义 first second 两个指针。
考虑到一些边界条件比如1->1->1->2这种情况需要把开头的几个1给去掉我们增加一个哑结点方便边界处理。

初始的两个指针如下:

将 first 指针指向哑结点
将 second 指针指向head (哑结点的下一个节点)
如果 first 指向的值不等于 second 指向的值则两个指针都前进一位
否则就单独移动 second second 不断往前走直到 first 指向的值不等于 second 指向的值。

比较逻辑 first.next.val == second.next.val

class Solution {
    /*
    执行结果通过

    执行用时0 ms, 在所有 Java 提交中击败了100.00%的用户
    
    内存消耗41.2 MB, 在所有 Java 提交中击败了33.05%的用户
    
    通过测试用例166 / 166
     */
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        //因为头节点也有可能被删除所有在这里定义一个哑节点 dummy
        ListNode dummy = new ListNode(-101);//给哑节点的值初始化到Node.val的范围之外
        dummy.next = head;
        //之所以在这里定义两个变量是为了代码的可读性更强。
        ListNode first = dummy;
        ListNode second = head;

        while (second != null && second.next != null) {
            //注意比较的逻辑
            if (first.next.val != second.next.val) {
                first = first.next;
                second = second.next;
            } else {
                //如果 first 和 second 指向的值相等则一直移动 second 直到不同为止
                while (second != null && second.next != null && first.next.val == second.next.val) {
                    second = second.next;
                }
                first.next = second.next;
                second = second.next;
            }
        }
        return dummy.next;
    }
}

方法二使用HashMap自己拓展写写试试。

LeetCode 1. 两数之和
LeetCode 2. 两数相加
LeetCode 3. 无重复字符的最长子串
LeetCode 4. 寻找两个正序数组的中位数
LeetCode 5. 最长回文子串
LeetCode 6. Z 字形变换
LeetCode 7. 整数反转
LeetCode 8. 字符串转换整数 (atoi)
LeetCode 9. 回文数
LeetCode 10. 正则表达式匹配
LeetCode 13. 罗马数字转整数
LeetCode 14. 最长公共前缀
LeetCode 20. 有效的括号本
LeetCode 26. 删除有序数组中的重复项
LeetCode 27. 移除元素
LeetCode 28. 找出字符串中第一个匹配项的下标
LeetCode 35. 搜索插入位置
LeetCode 53. 最大子数组和
LeetCode 66. 加一
LeetCode 67. 二进制求和
LeetCode 69. x 的平方根
LeetCode 70. 爬楼梯
LeetCode 80. 删除有序数组中的重复项 II
LeetCode 82. 删除排序链表中的重复元素 II