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

题意

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

回 已排序的链表 。

难度

简单

示例

示例 1：

083.%E5%88%A0%E9%99%A4%E6%8E%92%E5%BA%8F%E9%93%BE%E8%A1%A8%E4

%B8%AD%E7%9A%84%E9%87%8D%E5%A4%8D%E5%85%83%E7%B4%A0-

20230929082829.png

输入：head = [1,1,2]

输出：[1,2]

示例 2：

083.%E5%88%A0%E9%99%A4%E6%8E%92%E5%BA%8F%E9%93%BE%E8%A1%A8%E4

%B8%AD%E7%9A%84%E9%87%8D%E5%A4%8D%E5%85%83%E7%B4%A0-

20230929082839.png

输入：head = [1,1,2]

输出：[1,2]

分析

注意，本题跟 082.删除排序链表中的重复元素 II 很像，差别就是本题只需要保留一个重

复的元素，而 082 需要把所有重复的元素全部删除。

既然很像，那我们就可以采用同样的解题思路。

• 从链表头部 head 开始遍历整个链表。

• 检查当前节点（cur）和下一个节点（cur.next）的值。如果它们相同，则跳过下一个

节点（即删除 cur.next 节点）。通过 cur.next = cur.next.next 来实现。

• 如果当前节点和下一个节点的值不同，则移动 cur 到下一个节点。

来看题解。

/**

* Definition for singly-linked list.

* public class ListNode {

* int val;

* ListNode next;

* ListNode() {}

* ListNode(int val) { this.val = val; }

* ListNode(int val, ListNode next) { this.val = val; this.next = next; }

*}

*/

class Solution {

public ListNode deleteDuplicates(ListNode head) {

// 如果链表为空或只有一个节点，直接返回

if (head == null){

return null;

}

 // 初始化 cur 指针，从头结点开始

ListNode cur = head;

// 遍历链表，直到 cur 或 cur.next 为 null

while (cur.next != null) {

// 检查当前节点的值和下一个节点的值是否相同

if (cur.val == cur.next.val) {

// 如果相同，删除下一个节点（通过跳过下一个节点来实现）

cur.next = cur.next.next;

} else {

// 如果不同，将 cur 移动到下一个节点

cur = cur.next;

}

}

// 返回修改后的链表的头结点

return head;

}

}

我们来模拟一下整个过程。假设已排序的链表为: 1 -> 1 -> 2 -> 3 -> 3

初始化 cur 指向头节点。

[cur]1 -> 1 -> 2 -> 3 -> 3

首先，检查 cur 和 cur.next。它们的值都是 1，所以我们删除 cur.next 节点：

[cur]1 -> 2 -> 3 -> 3

然后，cur 指向的值（1）和其下一个节点的值（2）不相同。所以，移动 cur 到下一个节

点：

1 -> [cur]2 -> 3 -> 3

再次，cur 指向的值（2）和其下一个节点的值（3）不相同。所以，移动 cur 到下一个节

点：

1 -> 2 -> [cur]3 -> 3

现在，cur 和 cur.next 的值都是 3，所以我们删除 cur.next 节点：

1 -> 2 -> [cur]3

此时，cur.next 为空，停止循环。

最终链表为: 1 -> 2 -> 3

那这次我们不需要用到虚拟节点 grandFather 了，因为我们的题解必然会把第一个元素

保留下来，无论它重不重复。

来看一下题解的效率：

083.%E5%88%A0%E9%99%A4%E6%8E%92%E5%BA%8F%E9%93%BE%E8%A1%A8%E4

%B8%AD%E7%9A%84%E9%87%8D%E5%A4%8D%E5%85%83%E7%B4%A0-

20230929083846.png

总结

本题大致与 082.删除排序链表中的重复元素 II 一致，所不同的是，需要留下一个重复元

素，这是一道非常简单的链表题目，相信大家都能解出来。

力扣链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-list/