我的代码存在什么问题？删除无序链表中的重复元素

问题描述 #

给定一个包含N个节点的无序链表，任务是移除其中的重复元素。当某个值出现在多个节点中时，保留首次出现的节点，移除其他重复节点。

示例1 #

输入：
N = 4
value[] = {5,2,2,4}
输出：5 2 4

示例2 #

输入：
N = 5
value[] = {2,2,2,2,2}
输出：2

我的代码 #

def removeDuplicates(head):
        if head is None or not head.next:
            return head
        d = {}
        curr = head
        prev = None
        
        while curr.next:
            
            prev = curr
            curr = curr.next
            if curr.data in d:
                prev.next = curr.next
            else:
                d[curr.data] = 1
        return head

这段代码无法正确完成功能，问题出在哪里？

代码问题分析 #

你的代码主要有两个核心问题：

• 未将链表头节点的值存入哈希表
  哈希表d初始为空，而你的循环是从第二个节点开始遍历的，完全没处理头节点的data。这会导致如果后续节点出现和头节点相同的值时，无法识别为重复。比如示例2中，所有节点都是2，头节点的2没被加入哈希表，第二个节点的2会被判定为不在哈希表中而加入，后续节点才会被移除，但最终链表会剩下头节点和第二个节点，输出变成2 2，不符合预期。
• 删除节点后未正确更新curr指针
  当你通过prev.next = curr.next删除当前curr节点后，curr指针没有更新到新的节点（也就是原来的curr.next），而是在循环继续时执行curr = curr.next，这会跳过下一个节点，导致某些重复值可能没被检查到。比如链表是3->3->3，删除第二个3后，curr变成第三个3，然后循环结束，第三个3不会被检查到，最终链表剩下3->3。

修正后的代码示例 #

def removeDuplicates(head):
    if head is None or not head.next:
        return head
    d = {head.data: 1}  # 先存入头节点的值
    curr = head
    while curr.next:
        if curr.next.data in d:
            # 删除重复节点，curr不需要移动，因为下一个节点已经更新
            curr.next = curr.next.next
        else:
            d[curr.next.data] = 1
            curr = curr.next  # 只有当前节点不重复时才移动指针
    return head

内容的提问来源于stack exchange，提问作者Vishav Singla