单链表单次遍历实现删除最大最小值节点的代码修改求助

核心思路 #

由于要求仅单次遍历链表，且不能使用双向链表，我们需要在遍历过程中同时跟踪最小/最大值节点，以及它们的直接前驱节点。遍历结束后，通过前驱节点的指针修改完成删除操作，无需二次遍历。

实现步骤 #

1. 初始化跟踪变量：除了当前遍历节点和其前驱，还需记录最小节点、最大节点，以及它们各自的前驱节点，同时保留头节点的引用用于后续更新。
2. 单次遍历更新状态：遍历每一个节点时，对比当前值与已记录的最值，更新对应的节点和前驱引用。
3. 处理头节点删除：如果最值节点是原头节点，直接将新头节点指向该节点的下一个节点。
4. 完成节点删除：通过前驱节点的next指针跳过对应的最值节点，完成删除。注意处理最值节点相邻的特殊情况（遍历过程中已记录正确前驱，无需额外调整）。

代码示例（Python） #

假设链表节点定义为：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

实现函数：

def delete_min_max(head):
    # 空链表处理
    if not head:
        return (None, None, None)
    # 单节点链表处理（既是最小也是最大）
    if not head.next:
        return (None, head, head)
    
    # 初始化跟踪变量
    curr = head
    prev = None
    min_node = head
    max_node = head
    prev_min = None
    prev_max = None
    
    # 单次遍历链表，同步更新最值及前驱
    while curr:
        if curr.val < min_node.val:
            min_node = curr
            prev_min = prev
        if curr.val > max_node.val:
            max_node = curr
            prev_max = prev
        prev = curr
        curr = curr.next
    
    # 确定新的头节点
    new_head = head
    if min_node == new_head:
        new_head = min_node.next
    # 若最大节点是原头且不是最小节点（元素唯一，不会重复）
    if max_node == new_head and max_node != min_node:
        new_head = max_node.next
    
    # 删除最小节点
    if prev_min:
        prev_min.next = min_node.next
    # 删除最大节点（元素唯一，无需考虑与最小节点重复）
    if prev_max and max_node != min_node:
        prev_max.next = max_node.next
    
    # 返回新头、最小节点、最大节点
    return (new_head, min_node, max_node)

关键细节说明 #

• 前驱跟踪的必要性：单向链表无法反向访问节点，必须在遍历过程中记录最值节点的前驱，才能在遍历结束后直接修改指针完成删除。
• 头节点特殊处理：如果最值节点是头节点，没有前驱，需直接更新头节点引用。
• 元素唯一性保障：题目明确所有元素值唯一，因此无需处理最值节点为同一个的情况（仅单节点链表除外，已单独处理）。

内容的提问来源于stack exchange，提问作者Ash