设单链表已非递减有序排列,设计算法实现在单链表中删除值相同的多余节点。
时间: 2024-10-28 18:09:21 浏览: 34
将非递减有序的单链表中值相同的多余结点删除
5星 · 资源好评率100%
对于一个已经非递减有序排列的单链表,我们需要删除所有相邻且值相等的节点,只保留列表中的第一个出现的值。这个过程可以使用迭代或者递归的方式完成。这里提供一种简单的迭代解决方案:
1. 初始化两个指针,`prev` 和 `current` 分别指向头节点和第二个节点。
2. 当 `current` 不为空时,循环执行以下步骤:
a. 检查 `current` 的值是否等于 `prev` 的值。如果相等,则更新 `prev` 为 `current` 的下一个节点,并将 `current` 设置为空,因为我们要删除当前节点。
b. 如果值不相等,说明找到了一个新的不同值,将 `prev` 置为 `current`,然后继续移动到下一个节点,即 `prev = current`。
3. 最后,将头节点设置为 `prev`,因为 `prev` 指向的是第一个不重复的值。
下面是伪代码形式:
```python
def removeDuplicates(head):
if head is None or head.next is None:
return head
prev = head
current = head.next
while current is not None:
if current.val == prev.val:
prev.next = current.next
current = current.next
else:
prev = current
current = current.next
return head
```
阅读全文