给定一个带头节点的单链表，设计一个算法，实现一次遍历求出其最小值和次小值

Question

给定一个带头节点的单链表，设计一个算法，实现一次遍历求出其最小值和次小值

Answer 1

核心思路

1. 先处理边界情况：空链表、只有1个节点的情况，直接返回对应结果
2. 从第一个有效节点开始，初始化最小值和次小值，先找一个和最小值不同的节点来定初始次小值，保证最小值 < 次小值
3. 一次遍历剩下的节点，按规则更新：
   • 遇到比最小值还小的数 → 次小值继承原来的最小值，最小值更新成这个数
   • 遇到介于两者之间的数 → 直接更新次小值
   • 碰到和最小值一样的数，跳过，避免次小值重复

Python 代码实现

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

def find_min_second(head):
    # 空链表或只有头节点
    if not head.next:
        return (None, None)
    # 只有1个有效节点，没次小值
    if not head.next.next:
        return (head.next.val, None)

    current = head.next
    min_val = current.val
    second_min = None

    # 先找第一个和min_val不同的节点，初始化次小值
    current = current.next
    while current:
        if current.val != min_val:
            second_min = current.val
            # 保证min_val更小
            if second_min < min_val:
                min_val, second_min = second_min, min_val
            break
        current = current.next

    # 所有节点值都一样
    if not second_min:
        return (min_val, None)

    # 继续遍历剩下的节点
    current = current.next
    while current:
        val = current.val
        if val < min_val:
            second_min = min_val
            min_val = val
        elif min_val < val < second_min:
            second_min = val
        current = current.next

    return (min_val, second_min)

测试一下

# 构建链表：头→5→3→8→2→7
head = ListNode()
nodes = [ListNode(5), ListNode(3), ListNode(8), ListNode(2), ListNode(7)]
for i in range(len(nodes)-1):
    nodes[i].next = nodes[i+1]
head.next = nodes[0]

print(find_min_second(head))  # 输出 (2, 3)

这个算法时间复杂度O(n)，只遍历一次，空间复杂度O(1)，特别高效。