删除链表中的重复元素。

核心回答

若题意是“有序单链表中每个值保留一次”，重复值必然相邻。用cur扫描：cur与后继值相等时，让cur.next跳过后继，cur留在原处继续检查；不相等才前进。一次遍历O(n)，额外空间O(1)，原地修改链接。

开始前要确认两个条件：链表是否有序，以及重复值是保留一个还是全部删除。后一种题需要识别整段重复节点，不能直接套下面代码。

实现

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def delete_duplicates(head):
    cur = head
    while cur is not None and cur.next is not None:
        if cur.val == cur.next.val:
            cur.next = cur.next.next
        else:
            cur = cur.next
    return head

代码假设输入为有限、无环、按值非递减排列的单链表。Python解除本链上的引用不等于强制释放对象；如果别处还持有节点引用，节点仍可能存在。

为什么删除后cur不能立即前进

对1→1→1→2，第一次跳过后变成1→1→2。若cur立即前进到第二个1，就会漏掉它与已保留第一个1的重复关系。留在原处继续比较，才能删除整个重复段中的多余节点。

循环中，cur之前的部分已去重，cur是当前值保留的节点；每次操作要么删除一个尚未处理节点，要么向后移动一步，因此总处理次数为线性。空链表直接返回None，单节点不进入循环，全相同链表只保留头节点。

追问

如果无序呢？ 可用集合保存见过的值并跳过后续重复节点，平均O(n)时间、O(n)额外空间；若要求O(1)空间，则通常需要嵌套扫描，时间O(n²)。排序会改变原有顺序，应先确认允许。

如果重复值一个也不留呢？ 例如1→1→2应返回2，需要用哑节点和前驱识别整段重复值，头部也可能被删除。这是另一种题意。

C++需要delete吗？ 应按节点所有权约定释放被移除的节点，先保留其后继再释放，避免悬垂引用；共享或托管节点不能随意delete。

参考资料