难度: Medium
Submission
运行时间: 447 ms
内存: 44.1 MB
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:
hash = {}
prev = dummy = ListNode(-1, head)
cur = head
while cur:
if cur.val not in hash:
hash[cur.val] = False
else:
hash[cur.val] = True
cur = cur.next
cur = head
while cur:
if hash[cur.val]:
prev.next = cur.next
else:
prev.next = cur
prev = prev.next
cur = cur.next
return dummy.next
Explain
此题解采用哈希表来记录每个元素出现的情况。首先遍历一次链表，利用哈希表记录每个节点值是否重复（出现一次以上）。然后再次遍历链表，通过之前构建的哈希表检查每个节点的值是否重复，如果重复则从链表中移除该节点。为了便于操作链表头部（头节点可能被删除），使用了一个哑节点（dummy node）。
时间复杂度: O(n)
空间复杂度: O(n)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# this.val = val
# this.next = next
class Solution:
def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:
hash = {}
# 使用哑节点简化头部操作
prev = dummy = ListNode(-1, head)
cur = head
# 第一次遍历，记录每个值是否重复
while cur:
if cur.val not in hash:
hash[cur.val] = False
else:
hash[cur.val] = True
cur = cur.next
cur = head
# 第二次遍历，移除重复的节点
while cur:
if hash[cur.val]: # 如果当前值重复
prev.next = cur.next # 移除当前节点
else:
prev.next = cur # 保留当前节点
prev = prev.next # 移动prev指针
cur = cur.next
return dummy.next
Explore
在哈希表中，我通过使用一个布尔值跟踪每个节点值的出现状态。初始状态，当一个节点值首次出现时，在哈希表中该值对应的条目被设置为`False`，表示该值未重复。如果在后续的遍历中再次遇到相同的节点值，我将该值对应的条目更新为`True`，表明该值已重复。这样的设计可以在第二次遍历时快速检查每个节点值是否应被保留或移除。
在第二次遍历链表时，我使用`prev`指针始终指向最后一个未被删除的节点。当遇到一个需要被删除的节点时，我不会移动`prev`指针，而是直接将`prev.next`更新为`cur.next`，从而跳过当前节点。这样，无论当前节点是否被删除，`prev`指针都会正确地指向前一个有效节点。当不需要删除当前节点时，我更新`prev`为当前节点（即`prev = cur`），这样`prev`总是指向当前链表中的最后一个有效节点。
使用哑节点的主要目的是为了简化链表头部的操作，特别是当头节点有可能被删除时。哑节点被设置在链表的前端，其`next`指针指向原始链表的头节点。这样，在处理节点删除时，即使头节点被删除，哑节点的`next`指针可以轻松更新，从而保持链表的完整性。如果没有使用哑节点，我们需要额外处理头节点可能被删除的情况，这通常需要在删除操作前进行额外的判断，增加代码的复杂度和出错的可能性。
哈希表的实现在Python中是非常灵活的，可以处理各种类型的键值，包括整数、浮点数、字符串等。因此，即使节点的值是非整数类型，只要这些类型是可哈希的（即可以作为字典的键），这种方法仍然适用。需要注意的是，对于不可哈希的类型（如列表或其他可变类型），我们需要先将其转换为可哈希的类型，或者使用其他数据结构来实现类似的功能。