每日一道 LeetCode (18)：删除排序链表中的重复元素
❝每天 3 分钟，走上算法的逆袭之路。
❞
前文合集
代码仓库
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
解题思路
连续被数学题虐了两天，今天终于能看到一道正常的，普通智商可以解开的算法题了。
我太难了，每天晚上都被数学题虐的死去活来，一度让我精神恍惚，仿佛回到高三那一年。
题目要求给一个排序链表去重，这个链表已经是排好序的了，那么去重这件事儿就很简单了，只要重复，必定链表上的两个元素是相邻的，所以只需要在一个循环中判断相邻 n 和 n + 1 个元素是否相等就好，如果相等的话，那么元素 n 上的指针直接指向 n + 2 ，进行下一次循环，判断这两个元素是否相等。
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;
}
上面这种算法稍稍有点小问题，从示意图上可以看到， 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;
}
和第一种写法耗时维持一致，这个很正常，我们只是清除掉了不在使用的元素，并没有优化寻找方案，整体的时间复杂度还是保持了 O(n) 。
评论