现给定一个带头结点的单链表L,分别做如下处理: 01.编写伪代码将L就地逆置,所谓“就地”是指辅助空间复杂度为O(1)。 02.编写在L中删除一个最小值结点的高效算法(假设最小值结点唯一),并分析时间和空间复杂度。
时间: 2024-10-20 18:10:42 浏览: 28
nixu.rar_链表就地逆置
01. 就地逆置单链表的伪代码(空间复杂度为 O(1)):
```
function reverseList(L):
if L is empty or L只有一个元素:
return L
current = L; // 初始化当前节点为头节点
prev = None; // 初始化前驱节点为 null
while current is not None:
nextTemp = current.next; // 保存当前节点的下一个节点
current.next = prev; // 更新当前节点的指针,使其指向前驱
prev = current; // 更新前驱节点为当前节点
current = nextTemp; // 移动到下一个节点
L.head = prev; // 最后更新头节点为原头节点的前驱
return L;
```
02. 删除链表中最小值结点的高效算法(时间复杂度为 O(n),空间复杂度为 O(1)):
```python
def deleteMinNode(L):
if L is empty:
return None
# 如果头节点是最小值
if L.head.value > L.head.next.value:
min_node = L.head
L.head = L.head.next
else:
min_node = L.head.next
current = L.head
while current.next is not None:
if current.next.value < min_node.value:
min_node = current.next
current = current.next
# 删除找到的最小值节点
if min_node != L.head:
current.next = min_node.next
return L
```
阅读全文