单链表删除最大结点算法 Python 实现

本文介绍了在单链表中删除最大结点的算法，并提供了 Python 代码实现。该算法能够找到链表中的最大值结点，并将其删除，输出删除后的链表。代码示例易于理解，并包含详细的注释。

问题描述:

给定一个单链表，每个结点存放一个正整数，设计算法删除最大的结点，并输出删除后的链表。若最大值结点有若干个，删除第一个即可。

输入格式:

输入若干正整数，以-1作为结束。如：3 5 7 8 34 21 88 21 7 9 -1

输出格式:

输出删除最大值之后的链表。

算法示例:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

def delete_max_node(head):
    if not head:
        return None

    if not head.next:
        return None

    max_value = head.value
    max_prev = None
    current = head

    while current.next:
        if current.next.value > max_value:
            max_value = current.next.value
            max_prev = current
        current = current.next

    if max_prev:
        max_prev.next = max_prev.next.next
    else:
        head = head.next

    return head

def print_linked_list(head):
    current = head
    while current:
        print(current.value, end=' ')
        current = current.next
    print()

# 读取输入
values = list(map(int, input().split()))

# 创建链表
head = None
current = None
for value in values:
    if value == -1:
        break
    node = Node(value)
    if not head:
        head = node
        current = node
    else:
        current.next = node
        current = node

# 删除最大结点
head = delete_max_node(head)

# 输出链表
print_linked_list(head)

代码说明:

Node 类: 表示链表中的一个结点，包含 value 和 next 属性，分别存储结点的值和指向下一个结点的指针。
delete_max_node 函数: 接收链表的头结点作为参数，返回删除最大值结点后的链表头结点。
print_linked_list 函数: 接收链表的头结点作为参数，输出链表的所有结点的值。

代码解释:

初始化: 在 delete_max_node 函数中，首先判断链表是否为空或只有一个结点，如果是则直接返回。否则，将头结点的值设置为最大值，并初始化 max_prev 为 None，表示最大值结点之前没有结点。
遍历链表: 使用 while 循环遍历链表，如果当前结点的下一个结点的值大于当前最大值，则更新最大值和 max_prev。
删除最大值结点: 如果 max_prev 不为空，表示最大值结点在链表中间，则将 max_prev 指向最大值结点的下一个结点。如果 max_prev 为空，表示最大值结点是头结点，则将 head 指向下一个结点。
输出结果: 使用 print_linked_list 函数输出删除最大值结点后的链表。

注意:

这里的代码适用于在 Python 环境中运行。
可以将输入的正整数以空格分隔的形式输入，以-1作为结束符。
代码中使用了 None 来表示空指针。

示例输入:

3 5 7 8 34 21 88 21 7 9 -1

示例输出:

3 5 7 8 34 21 21 7 9

希望以上解释能够帮助您理解该算法和 Python 代码实现。如果您有任何问题，请随时提出。