Salesforce 链表去重：保留每个整数首次出现的节点

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 输入为有限无环单链表，每个节点含整数 data 和 next；返回头节点。保留原有首个节点的身份与顺序，移除重复值的后续节点。
• 可以使用额外哈希集合，代码不复制存活节点。若面试官禁止额外空间，应另讨论 O(n²) 扫描或排序破坏顺序的问题。
• 移除节点时将其 next 断开，方便明确所有权与测试；实际语言的内存释放责任需与节点 API 约定，题目未说明。

解题路线

1. 维护 seen 值集合、previous 为最后一个保留的节点、current 为下一个待检查节点。每轮先保存 following=current.next，避免改链后丢失未处理后缀。
2. 若 current.data 已在 seen，令 previous.next=following 并断开 current；previous 不动。否则把值加入 seen，令 previous=current。最后令 current=following。
3. 循环不变量：从 head 到 previous 的链恰好由已扫描前缀中每个值首次出现的原节点组成，顺序不变；seen 恰好记录这些值。每轮处理一个节点，所以遍历终止且结果符合题意。

手动走一遍

3→4→3→6：先保留首个 3 与 4，seen={3,4}；到第二个 3 时，把 4.next 从该节点改指向 6，保留链成 3→4→6；最后保留 6。输入 2→2→2 时只保留第一个 2；空链表返回 None。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from dataclasses import dataclass


@dataclass
class Node:
    data: int
    next: "Node | None" = None


def condense(head: Node | None) -> Node | None:
    """Keep each integer's first node, preserving surviving node identity."""
    seen: set[int] = set()
    previous: Node | None = None
    current = head
    while current is not None:
        following = current.next
        if current.data in seen:
            assert previous is not None
            previous.next = following
            current.next = None
        else:
            seen.add(current.data)
            previous = current
        current = following
    return head

复杂度

n 为节点数、u 为不同整数个数。每节点检查一次，哈希集合均摊时间 O(n)、额外空间 O(u)；最坏哈希冲突行为依赖实现。若不允许额外集合且需保留顺序，可对每个节点向前扫描已保留值，时间最坏 O(n²)、辅助空间 O(1)。

易错点与追问

容易失分的边界

• 删除重复节点后仍把 previous 移向已删除节点，下一次改链会断开正确结果。
• 未先保存 current.next 就清空节点指针，失去后续链表入口。
• 用 set 重新构建节点，虽然值正确却破坏原节点身份和原地修改要求。
• 忽略空输入、全部相同值或重复值连续出现的情况。
• 把‘保留第一次出现’理解成保留最后一次出现，导致示例节点身份与顺序不符。

继续深挖

• 若禁用额外空间，怎样以 O(n²) 时间扫描已保留前缀，同时保持原节点顺序？
• 若链表已经按值排序，可只比较相邻节点，以 O(n) 时间、O(1) 空间完成，但本题题目没有排序条件。
• 若可能存在环，先做环检测并约定拒绝或修复；直接遍历会无限循环。