设L为带头结点的单链表,表中元素值递增有序,编写程序删除表中值相同的多余元素
时间: 2024-10-11 19:17:47 浏览: 48
删除单链表中值相同的多余元素的算法通常涉及遍历链表并维护两个指针,一个普通指针`current`,一个用于比较当前值的`prev`指针。以下是Python的一个简单实现:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def remove_duplicates(head):
if not head or not head.next:
return head
current = head
prev = None
while current:
if prev and prev.val == current.val:
# 如果当前节点的值与前一个节点相同,删除当前节点
prev.next = current.next
else:
prev = current
current = current.next
return head
```
这个函数首先检查链表是否为空或只有一个元素。然后设置`prev`为None,`current`为头节点开始遍历。如果`prev`存在并且其值等于`current`的值,那么就将`prev`的`next`指向`current`的下一个节点,跳过当前节点;否则,更新`prev`为`current`以便下一次比较。
阅读全文