☆打卡算法☆LeetCode 83、删除排序链表中的重复元素 算法解析

一、题目

1、算法题目

“ 给定一个排序的链表，删除重复的元素，使每个元素出现一次，返回排序后的链表。”

题目链接：

来源：力扣（LeetCode）

链接：83. 删除排序链表中的重复元素 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

image.png

示例 1：
输入： head = [1,1,2]
输出： [1,2]

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

二、解题

1、思路分析

这道题跟82题 删除排序链表中的重复元素 II 很像，不仅是名字像，题型也像。

82题是删除所有重复元素，83题是删除重复元素，每个元素只出现一次，还是可以根据82题的解题思路来。

由于链表是排好序的，重复的元素在链表中出现的位置一定是连续的，对链表进行一次遍历，删除重复的元素吗，就可以得到我们想要的结果。

用指针cur指向头节点，如果cur和cur.next元素相同，那么我们就将cur.next从链表中删除，否则就说明链表中不存在其他重复的元素，直接返回这个链表即可。

2、代码实现

代码参考：

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }

        ListNode cur = head;
        while (cur.next != null) {
            if (cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }

        return head;
    }
}

image.png

3、时间复杂度

时间复杂度 ： O(n)

其中n是链表的长度。

空间复杂度： O(1)

三、总结

这道题的关键在于去重，并且重复的元素一定是重复的这个要点去解题。

那么就可以一直指针指向头部，判断下一个指针的下一个节点是否是重复元素，重复就删除，不重复就移动到下一位继续。

如此，循环到最后就得到了我们想要的链表了。