在带有头结点单链表中存储了多个整型数据,设计算法,找到最大值并将之从链表中删除。给出完整代码
时间: 2024-09-13 20:19:14 浏览: 33
试写出一个计算单链表中结点个数的算法,其中指针p指向该链表的第一个结点。
在单链表中查找最大值并删除的过程通常包括三个步骤:遍历链表找到最大值、更新最大值节点的位置以及实际删除最大值节点。这里是一个简单的Python示例,假设我们有一个名为`ListNode`的链表节点结构,包含整数值`val`和指向下一个节点的指针`next`:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def find_max_and_delete(head):
# 初始化最大值和当前节点
max_val = head.val if head else float('-inf')
current = head
# 遍历链表,找到最大值并更新位置
while current is not None:
if current.val > max_val:
max_val = current.val
max_node = current # 更新最大值节点
current = current.next
# 删除最大值节点
if max_node == head:
head = head.next
else:
max_node.next = max_node.next.next
return max_val, head
# 示例用法
# 创建链表 [1, 3, 5, 9, 7]
head = ListNode(1)
head.next = ListNode(3)
head.next.next = ListNode(5)
head.next.next.next = ListNode(9)
head.next.next.next.next = ListNode(7)
max_value, new_head = find_max_and_delete(head)
print("最大值:", max_value)
print("删除后的链表:", [node.val for node in new_head])
```
在这个代码中,首先初始化最大值为链表的第一个元素,然后遍历整个链表,如果遇到比当前最大值大的元素,就更新最大值和最大值节点。遍历结束后,根据找到的最大值节点的位置删除它。
阅读全文