1. 首页
  2. LeetCode

每日一道 LeetCode (18):删除排序链表中的重复元素

每日一道 LeetCode (18):删除排序链表中的重复元素

每天 3 分钟,走上算法的逆袭之路。

前文合集

每日一道 LeetCode 前文合集

代码仓库

GitHub: https://github.com/meteor1993/LeetCode

Gitee: https://gitee.com/inwsy/LeetCode

题目:删除排序链表中的重复元素

题目来源:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/

给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。

示例 1:

输入: 1->1->2
输出: 1->2

示例 2:

输入: 1->1->2->3->3
输出: 1->2->3

解题思路

连续被数学题虐了两天,今天终于能看到一道正常的,普通智商可以解开的算法题了。

我太难了,每天晚上都被数学题虐的死去活来,一度让我精神恍惚,仿佛回到高三那一年。

题目要求给一个排序链表去重,这个链表已经是排好序的了,那么去重这件事儿就很简单了,只要重复,必定链表上的两个元素是相邻的,所以只需要在一个循环中判断相邻 nn + 1 个元素是否相等就好,如果相等的话,那么元素 n 上的指针直接指向 n + 2 ,进行下一次循环,判断这两个元素是否相等。

每日一道 LeetCode (18):删除排序链表中的重复元素

public ListNode deleteDuplicates(ListNode head) {
    ListNode current = head;
    while (current != null && current.next != null) {
        if (current.val == current.next.val) {
            current.next = current.next.next;
        } else {
            current = current.next;
        }
    }
    return head;
}

每日一道 LeetCode (18):删除排序链表中的重复元素

上面这种算法稍稍有点小问题,从示意图上可以看到, n + 1 这个元素的指针还指向了 n + 2 ,如果链表比较大,会产生很多的 「野指针」 ,这段代码稍微改一下,我们把删掉不用的元素置空:

public ListNode deleteDuplicates_1(ListNode head) {
    ListNode current = head;
    while (current != null && current.next != null) {
        if (current.val == current.next.val) {
            ListNode node = current.next;
            current.next = node.next;
            node.next = null;
        } else {
            current = current.next;
        }
    }
    return head;
}

每日一道 LeetCode (18):删除排序链表中的重复元素

和第一种写法耗时维持一致,这个很正常,我们只是清除掉了不在使用的元素,并没有优化寻找方案,整体的时间复杂度还是保持了 O(n) 。

转载声明:本博客由极客挖掘机创作,采用 CC BY 3.0 CN 许可协议。可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在文末添加作者公众号二维码。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

QR code