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

Categories:

Tags:

题目描述
思路分析
1. 解法一：单指针原地去重（推荐）
相似题目

题目描述

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

思路分析

解法一：单指针原地去重（推荐）

核心思路：

链表已有序，重复元素必然相邻。用单指针 cur 从头遍历：

若 cur.val == cur.next.val：跳过 cur.next，令 cur.next = cur.next.next（cur 不前进，因为新的 next 还可能重复）

否则：cur = cur.next（当前节点唯一，安全前进）

头节点不会被删除（有序链表，头节点是最小值），直接返回原 head，无需哨兵节点。

与 82 题的区别：82 题要删除所有重复节点（包括第一次出现的），需要哨兵节点；本题只保留重复节点的第一个，无需哨兵。

复杂度分析：

时间复杂度：O(n)，其中 n 是链表长度，每个节点最多访问一次

空间复杂度：O(1)，只使用常数个指针变量

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            if (cur.val == cur.next.val) {
                // 跳过重复节点，保留当前节点，cur 不前进（新 next 仍可能重复）
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }
}

func deleteDuplicates(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	cur := head
	for cur != nil && cur.Next != nil {
		if cur.Val == cur.Next.Val {
			// 跳过重复节点，cur 不前进（新 Next 仍可能重复）
			cur.Next = cur.Next.Next
		} else {
			cur = cur.Next
		}
	}
	return head
}

相似题目

题目	难度	考察点
82. 删除排序链表中的重复元素 II	中等	删除所有重复节点
26. 删除有序数组中的重复项	简单	数组原地去重
80. 删除有序数组中的重复项 II	中等	数组去重最多保留两个
203. 移除链表元素	简单	链表节点删除
27. 移除元素	简单	数组原地移除指定值
19. 删除链表的倒数第 N 个结点	中等	快慢指针定位删除

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/00102071