试写一算法,删除元素非递减排列的单链表L中所有值相同的元素。即相同元素值只保留一个。
时间: 2024-10-07 13:08:01 浏览: 29
已知线性表中的元素以值递增有序排列,并以单链表作存储结构。试写一高效的算法,删除表中所有值相同的多余元素(使得操作后的线性表中所有元素的值均不相同)
为了删除元素非递减排列的单链表L中所有值相同的元素,我们可以使用迭代的方式实现一个算法。假设我们有一个指向链表头节点的指针`head`。以下是算法步骤:
1. 定义两个指针`current`和`prev`,分别初始化为`head`和`NULL`。`current`用于遍历链表,`prev`用于存储当前元素的前一个元素。
2. 遍历链表:
a. 当`current`不为空时,执行以下操作:
i. 检查`current`的值是否等于`prev`的值。如果相等,说明有连续的重复元素,跳过`current`,并将其从链表中删除。
- 移动`prev`到`current`的下一个节点(`prev = current.next;`)
- 删除`current`(`current = current.next;`),因为`prev`已经指向了下一个节点
ii. 如果值不相等,将`prev`更新为`current`,准备检查下一个元素的值。
3. 当`current`变为`NULL`时,`prev`就是链表的新头部,因为它是最前面的唯一值。
```python
def delete_duplicates(head):
if head is None or head.next is None:
return head
current = head
prev = None
while current is not None:
next_temp = current.next
# 检查是否有重复值
if current.value == prev.value:
# 跳过重复值
current = next_temp
else:
# 更新前驱节点和当前节点
prev = current
current = next_temp
# 返回新的链表头部
return prev
```
阅读全文