LeetCode 83题《删除排序链表中的重复元素》是一道非常经典的链表基础题。

---

题目描述：有序链表去重 (Remove Duplicates)

【题目描述】 给定一个已排序（非降序）的单向链表，链表中包含 $N$ 个节点。请删除链表中所有重复出现的元素，使得每个元素只出现一次。返回处理后的链表头节点，并按顺序输出链表中的元素。

【输入格式】 第一行包含一个整数 $N$，表示链表的节点个数。 第二行包含 $N$ 个整数，表示链表节点的值。输入保证这些值是按照非降序排列的。

【输出格式】 输出一行，包含若干个整数，表示去重后的链表元素值，整数之间用空格分隔。

【样例 1】 输入：

3
1 1 2

输出：

1 2

【样例 2】 输入：

5
1 1 2 3 3

输出：

1 2 3

【数据范围与提示】

• 链表长度 $N$ 的范围：$[0, 300]$。
• 节点值的范围：$[-100, 100]$。
• 题目保证链表已经按升序排列。

---

一、 预备知识点总结

在解决这道题之前，你需要掌握以下 C++ 基础：

1. 结构体 (struct)：如何自定义一个链表节点（通常包含 val 和 next 指针）。
2. 指针 (Pointer)：
   • 理解 head（头指针）和 next（后继指针）的含义。
   • 掌握 -> 运算符访问成员。
   • 理解 nullptr（空指针）的判定。
3. 动态内存分配 (new/delete)：虽然竞赛中有时可以用静态数组模拟链表，但这道题的考点在于指针操作，建议使用 new。
4. 循环结构 (while/for)：用于遍历链表。

---

二、 读题关键词分析

拿到题目，先圈出这几个关键词，它们决定了你的算法设计：

1. “已排序” (Sorted)：
   • 教练解读：这是最重要的提示！这意味着重复的元素一定是在位置上相邻的。你不需要用哈希表（Hash Set）去记录出现过的数字，只需要盯着“当前节点”和“下一个节点”看就够了。
2. “删除” (Delete/Remove)：
   • 教练解读：在链表中删除一个节点，本质上是修改指针的指向，跳过那个不需要的节点。
3. “链表” (Linked List)：
   • 教练解读：不能像数组那样用下标 a[i] 访问。只能顺藤摸瓜，通过 next 指针一步步走。

---

三、 启发式图解思路（草稿纸教学）

好，拿出一张草稿纸，我们来画图模拟一下。假设输入数据是 1 -> 1 -> 2 -> 3 -> 3。

步骤 1：初始化 我们用一个指针 cur (current) 指向链表的头部。

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

步骤 2：比较与决策 问题：cur 指向的值是 1，cur->next 指向的值也是 1。它们相等吗？ 回答：相等！说明第二个 [1] 是多余的。

操作：我们要把第二个 [1] 删掉。怎么删？让 cur 的 next 指针直接越过第二个 [1]，指向 [2]。

[cur]       (断开)
  ↓           /
[ 1 ] ------------------> [ 2 ] ---> [ 3 ] ---> [ 3 ] ---> nullptr
              (跳过了中间的1)

教练提醒：这时候 cur 还是指向第一个 [1]。千万不要急着把 cur 往后移！ 为什么？因为有可能后面还有第三个 1（比如 1->1->1）。如果你移走了，就漏判了。

步骤 3：再次比较 现在 cur 指向 1，cur->next 指向 2。 问题：1 和 2 相等吗？ 回答：不相等。

操作：既然不重复，那当前节点 cur 是安全的。我们把 cur 往后移动一位。

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

步骤 4：继续循环 同理，cur 在 2，cur->next 是 3。不相等，cur 后移。

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

步骤 5：处理尾部 cur 在第一个 3，cur->next 是第二个 3。相等！删除后一个 3。 cur->next 变成了 nullptr。

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

循环结束条件：当 cur 为空，或者 cur 后面没有节点（cur->next == nullptr）时，停止。

---

四、 复杂度分析与优化

1. 时间复杂度：

   • 我们只遍历了一遍链表。
   • 每个节点最多被访问一次。
   • 所以是 $O(N)$，其中 $N$ 是节点数量。这是线性的，非常高效。

2. 空间复杂度：

   • 我们只是用了几个指针变量（cur 等），没有开辟新的数组或链表。
   • 所以是 $O(1)$（原地操作）。

---

五、 NOI竞赛风格参考代码 (C++14)

以下代码符合 NOI 竞赛标准，包含完整的头文件、结构体定义、输入构建链表、处理逻辑和输出销毁。

/**
 * NOI/NOIP 基础训练 - 链表去重
 * 语言: C++14
 * 风格: 标准竞赛风格
 */

#include <iostream>
#include <cstdio>

using namespace std;

// 定义链表节点结构体
struct ListNode {
    int val;
    ListNode *next;
    
    // 构造函数，方便初始化
    ListNode(int x) : val(x), next(nullptr) {}
};

/**
 * 核心逻辑函数：删除重复元素
 * 对应 LeetCode 的 deleteDuplicates 函数
 */
ListNode* deleteDuplicates(ListNode* head) {
    // 边界条件：如果是空链表或只有一个节点，直接返回
    if (head == nullptr || head->next == nullptr) {
        return head;
    }

    ListNode* cur = head;
    
    // 遍历链表，直到当前节点是最后一个节点为止
    while (cur->next != nullptr) {
        // 如果当前节点值等于下一个节点值
        if (cur->val == cur->next->val) {
            ListNode* duplicateNode = cur->next; // 暂存要删除的节点
            cur->next = cur->next->next;         // 修改指针，跳过重复节点
            
            // 在实际工程或严谨的C++中，应该释放 duplicateNode 的内存：
            // delete duplicateNode; 
            // 但在竞赛中，如果没有严格内存限制，有时会省略 delete 以节省时间，
            // 这里为了规范，建议大家养成好习惯。
            delete duplicateNode;
        } else {
            // 如果不相等，指针后移
            cur = cur->next;
        }
    }
    
    return head;
}

int main() {
    // 优化 I/O 速度，虽然本题数据量小不需要，但养成习惯
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0; // 读取节点数量

    if (n == 0) {
        // 处理 0 个节点的情况
        return 0;
    }

    // --- 构建链表 (尾插法) ---
    ListNode* head = nullptr;
    ListNode* tail = nullptr;

    for (int i = 0; i < n; ++i) {
        int val;
        cin >> val;
        ListNode* newNode = new ListNode(val);
        
        if (head == nullptr) {
            head = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
    }

    // --- 执行去重算法 ---
    head = deleteDuplicates(head);

    // --- 输出结果 ---
    ListNode* cur = head;
    bool first = true;
    while (cur != nullptr) {
        if (!first) cout << " ";
        cout << cur->val;
        first = false;
        
        // 竞赛结束后通常操作系统会回收内存，
        // 但为了演示完整性，这里可以暂存指针并在之后释放，
        // 或者简单地只做输出。
        cur = cur->next;
    }
    cout << endl;

    return 0;
}

总结辅导

同学们，这道题的难点不在于算法（仅仅是比较相邻元素），而在于指针的操作细节：

1. 判空保护：访问 cur->next->val 之前，必须保证 cur 和 cur->next 都不是 nullptr。
2. 循环不变量：只有当 cur->val != cur->next->val 时，cur 才向后移动；否则 cur 保持不动，继续检查新的 next。

把这两个细节写在你的代码规范本上，这道题你就完全掌握了！