一、问题描述

给定一个未排序的单链表，要求移除链表中的重复节点，同时保留最开始出现的节点。

示例

• 示例 1
  输入：[1, 2, 3, 3, 2, 1]
  输出：[1, 2, 3]

• 示例 2
  输入：[1, 1, 1, 1, 2]
  输出：[1, 2]

约束条件

• 链表长度范围：[0, 20000]
• 链表节点的值范围：[0, 20000]

进阶问题

如果不得使用临时缓冲区（如哈希表），该如何解决？

---

二、解题思路

思路一：双指针法

定义两个指针current和p，分别用于遍历链表。current指针用于逐个节点检查，p指针用于检查current之后的节点是否有重复值。如果发现重复值，则删除该节点。

思路二：哈希表法

利用哈希表（数组）记录每个节点值是否出现过。遍历链表时，检查当前节点值是否已在哈希表中标记，若已标记则删除该节点，否则标记该值。

---

三、代码实现

方法一：双指针法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeDuplicateNodes(struct ListNode* head) {
    if (head == NULL) return NULL;
    struct ListNode* current = head;
    while (current) {
        struct ListNode* p = current;
        while (p->next) {
            if (p->next->val == current->val) {
                // 删除重复节点
                p->next = p->next->next;
            } else {
                p = p->next;
            }
        }
        current = current->next;
    }
    return head;
}

方法二：哈希表法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeDuplicateNodes(struct ListNode* head) {
    if (head == NULL || head->next == NULL)
        return head;
    
    int hash[20001] = {0}; // 哈希表，标记节点值是否出现过
    hash[head->val] = 1;   // 标记头节点值

    struct ListNode* current = head;
    struct ListNode* next = head->next;

    while (next) {
        if (hash[next->val]) {
            // 如果当前节点值已出现过，删除该节点
            current->next = next->next;
            next = current->next;
        } else {
            // 标记当前节点值，并移动指针
            hash[next->val] = 1;
            current = current->next;
            next = next->next;
        }
    }
    return head;
}

---

四、复杂度分析

方法一：双指针法

• 时间复杂度：O(n²)，其中n为链表长度。每个节点都需要与后续节点进行比较。
• 空间复杂度：O(1)，不需要额外的存储空间。

方法二：哈希表法

• 时间复杂度：O(n)，只需遍历一次链表。
• 空间复杂度：O(m)，其中m为链表节点值的范围（本题中为20001）。

---

五、总结

本题提供了两种解法：双指针法和哈希表法。双指针法适用于不使用额外存储空间的场景，但时间复杂度较高；哈希表法则通过额外空间换取时间效率，适合对时间要求较高的场景。根据实际需求选择合适的解法。