难度: Easy
编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
示例1:
输入：[1, 2, 3, 3, 2, 1] 输出：[1, 2, 3]
示例2:
输入：[1, 1, 1, 1, 2] 输出：[1, 2]
提示：
- 链表长度在[0, 20000]范围内。
- 链表元素在[0, 20000]范围内。
进阶：
如果不得使用临时缓冲区，该怎么解决？
Submission
运行时间: 68 ms
内存: 20.6 MB
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeDuplicateNodes(self, head: ListNode) -> ListNode:
if head is None or head.next is None:
return head
pre = head
cur = head.next
s = {pre.val}
while cur:
if cur.val in s:
pre.next = pre.next.next
else:
pre = pre.next
s.add(cur.val)
cur = pre.next
return head
Explain
该题解采用哈希表来存储已经出现过的节点的值，以此来检测重复的节点。首先判断如果链表为空或者只有一个节点，则直接返回链表头部。使用两个指针，pre 和 cur，分别表示当前节点的前一个节点和当前节点。pre 初始化为头节点，cur 初始化为头节点的下一个节点。遍历链表，并使用集合 s 存储已经访问过的节点值。在遍历过程中，如果 cur 指向的节点的值在集合 s 中，说明该值已存在，需要将其从链表中移除，即通过修改 pre 的 next 指针实现。如果 cur 指向的节点的值不在集合中，则将该值加入集合，并将 pre 指针移动到 cur。这个过程一直持续到链表末尾。
时间复杂度: O(n)
空间复杂度: O(n)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeDuplicateNodes(self, head: ListNode) -> ListNode:
if head is None or head.next is None: # 检查链表为空或只有一个元素的情况
return head
pre = head # 初始化前一个节点为头节点
cur = head.next # 初始化当前节点为第二个节点
s = {pre.val} # 初始化集合并添加头节点的值
while cur: # 遍历链表
if cur.val in s: # 如果当前节点的值已存在于集合中
pre.next = pre.next.next # 移除当前节点
else:
pre = pre.next # 移动前一个节点指针
s.add(cur.val) # 将当前节点的值加入集合
cur = pre.next # 移动当前节点指针
return head
Explore
使用哈希表来存储节点值的主要优势在于其高效的查找、插入和删除操作，通常这些操作的时间复杂度为O(1)。相比之下，如果使用数组存储节点值，则在查找一个值是否存在时的时间复杂度为O(n)，因为可能需要遍历整个数组。使用链表存储节点值虽然插入操作较快（尤其是在链表头部插入），但查找和删除操作的时间复杂度同样为O(n)，因为可能需要遍历链表来查找或删除一个节点。因此，哈希表在处理此类问题时，提供了更高的效率和更快的响应速度。
在题解中，如果发现当前节点`cur`的值已经存在于集合中，节点的移除是通过修改前一个节点`pre`的`next`指针来实现的，具体是将`pre.next`设置为`pre.next.next`。这样，`cur`节点就被从链表中断开，因此被实际移除。如果`pre.next`已经是`None`，这意味着已经到达链表的末尾，不会再有节点需要检查或移除，因此这种情况下不需要特别操作。
在移除重复节点时，修改`pre.next`足以从链表中断开当前节点`cur`，因此`cur`节点已经被移除。之后，代码中`cur`指针会更新为`pre.next`，即指向下一个待检查的节点。这样的处理确保了`cur`指针总是指向正确的当前节点，而不需要额外的操作来维护或重置`cur`指针。这种方法简化了逻辑并保持了代码的整洁性。
当链表只有一个元素时，由于没有其他节点，因此不可能存在重复的值。直接返回头节点是合理的，因为没有任何更改需要应用于链表。这种处理方式适用于所有单节点链表的情况，确保了算法的正确性和效率。