LeetCode 83. Remove Duplicates from Sorted List

题目描述

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

解题思路

本题要求删除排序链表中的重复元素。由于链表已经排序，重复元素必然相邻，因此只需要遍历链表，比较当前节点和下一个节点的值是否相同。

核心思路：

1. 首先处理特殊情况：如果链表为空（head == null），直接返回 null。
2. 保存头节点指针 res，用于最终返回结果。
3. 遍历链表，当 head.next 不为空时：
   • 如果当前节点值等于下一个节点值（head.val == head.next.val），说明找到了重复元素，将当前节点的 next 指针跳过下一个节点，直接指向下下个节点（head.next = head.next.next）。注意这里使用 continue 而不是移动 head，因为可能需要连续删除多个重复元素（例如 1 → 1 → 1 → 2）。
   • 如果值不相同，正常移动指针到下一个节点（head = head.next）。

这种做法的关键是：当删除一个重复节点后不立即移动指针，这是因为被跳过的那个节点后面的新节点可能仍然与当前节点值相同，需要继续判断。

复杂度分析

• 时间复杂度：O(n)，其中 n 是链表节点数。每个节点最多被访问一次。
• 空间复杂度：O(1)，只使用了常数级别的额外空间（几个指针变量）。

代码

package code.J83;

import datastructure.ListNode;

public class J83 {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode res = head;
        if (head == null){
            return null;
        }
        while (head.next != null){
            if (head.val == head.next.val) {
                head.next = head.next.next;
                continue;
            }
            head = head.next;
        }
        return res;
    }
}