设计一种方法, 从无序链表中删除重复项, 保留第一次出现的节点。
时间: 2024-09-18 22:17:59 浏览: 25
设计一种方法从无序链表中删除重复项并保留首次出现的节点,可以采用迭代的方式实现。这里是一个基本步骤的描述:
1. 定义两个指针,`current` 和 `previous`,分别初始化为链表的头节点。
2. 遍历链表,对于每个节点:
- 检查当前节点的值是否等于 `previous` 节点的值。如果相等,则说明这是重复节点,将 `previous` 的下一个节点指向当前节点的下一个节点(跳过重复部分)。
- 如果不相等,则将 `previous` 更新为当前节点,准备处理下一个节点。
3. 当遍历结束后,`previous` 就会停在最后一个非重复节点上,因此链表的头节点就是去重后的链表的开始。
以下是伪代码示例:
```python
def deleteDuplicates(head):
if not head or not head.next:
return head
current = head
previous = None
while current:
if previous and current.val == previous.val:
# 删除重复项
previous.next = current.next
else:
# 保存非重复节点
previous = current
current = current.next
return head
```