我们可以使用哈希表来跟踪已经出现的节点值,从而删除重复项。我们可以遍历链表,对于每个节点,检查其值是否已经在哈希表中出现。如果节点值已经存在,则跳过该节点并将其前一个节点的next指针指向下一个不同的节点。如果节点值不存在,则将其添加到哈希表中。
以下是实现此解决方案的Python代码示例:
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def removeDuplicates(head: ListNode) -> ListNode:
if not head:
return None
visited = set()
visited.add(head.val)
prev = head
while prev.next:
curr = prev.next
if curr.val in visited:
prev.next = curr.next
else:
visited.add(curr.val)
prev = curr
return head
时间复杂度:O(n),空间复杂度:O(n)。