写一算法将单链表中值重复的结点删除,使所得 的结果链表中所有结点的值均不相同。
时间: 2024-09-21 12:01:12 浏览: 47
删除单链表中值相同的多余结点的算法
要编写一个算法来删除单链表中值重复的节点,使其结果链表中的所有节点值均唯一,你可以采用这样的步骤:
1. 定义两个指针 `prev` 和 `current`,初始都指向链表的头节点。
2. 创建一个新的空链表 `new_head` 作为结果链表的头部。
3. 使用循环遍历原始链表:
- 当 `current` 指针不为空时:
a. 检查 `current->data` 是否等于 `prev->data`(即当前节点的值是否和前一个节点的值相同)。
b. 如果不同,将 `prev` 指针移到 `current`,然后继续下一次迭代。
c. 如果相同,说明找到一个重复的节点,将 `prev` 更新为其下一个节点并继续遍历,因为重复节点后面的节点都是重复的。
4. 当遍历完成后,`prev` 就会停在最后一个非重复节点处,将其设置为新链表的尾部 (`new_head = prev`)。
5. 返回 `new_head` 作为新的链表头。
```python
def delete_duplicates(head):
if not head or not head.next:
return head
new_head = None
prev = current = head
while current:
if current.data != prev.data:
prev = current
else:
while current and current.data == prev.data:
current = current.next
prev.next = current
prev = current
current = current.next
return new_head
```
阅读全文