设计一个高效的算法,删除非空单链表L中的(一个)最小值。写出代码
时间: 2024-10-16 15:16:27 浏览: 24
设计一个高效算法来删除单链表L中的最小值,可以采用迭代或者递归的方式。这里我们提供一个迭代的解决方案:
首先,我们需要定义一个结构体来表示链表节点:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
```
然后我们可以创建一个函数`remove_min()`来进行操作:
```python
def remove_min(head):
if not head or not head.next: # 如果链表为空或只有一个元素
return None
current = head # 初始化当前节点为头节点
min_val = current.val # 最小值初始化为头节点的值
while current.next:
if current.next.val < min_val: # 如果找到更小的值
min_val = current.next.val
temp = current.next # 记录下这个新的最小节点
current = current.next # 移动到下一个节点
# 删除找到的最小节点
if current == head:
head = head.next
else:
current.next = current.next.next
return head
```
这个算法的时间复杂度是O(n),其中n是链表的长度,因为我们只遍历了一次链表。空间复杂度是O(1),因为我们只需要常数级别的额外空间。
阅读全文