合并两个有序链表的Python代码问题排查与正确实现思路求助

原代码核心问题 #

• 返回值固定为head_1，如果第二个链表的头节点值更小，合并后的链表头实际是head_2，直接返回head_1会丢失前面的节点
• 循环内的节点拼接逻辑完全颠倒：判断出current_h1值更小时，反而把current_h2拼接到结果链表尾部，完全不符合有序合并的要求
• 多余的current_h1.val != tail_to_use.val判断逻辑无意义，会导致相等值无法处理、节点重复校验的问题
• 初始选择完更小的头节点作为tail_to_use后，没有将对应链表的当前指针后移，导致头节点被重复判断

正确实现思路 #

合并两个升序有序链表的标准逻辑如下：

1. 新增一个虚拟哨兵节点作为结果链表的临时头，不用单独判断两个输入链表哪个头更小，简化边界处理
2. 用一个cur指针跟踪结果链表的当前尾部节点
3. 同时遍历两个输入链表，每次比较两个链表的当前节点值，将值更小的节点拼接到cur的下一位，然后将对应链表的遍历指针后移一位
4. 当其中一个链表遍历完成后，直接把另一个链表剩余的所有节点拼接到结果链表尾部
5. 最终返回虚拟哨兵节点的next属性，就是合并后的有序链表头节点

修正后的可运行代码 #

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

def merge_lists(head_1, head_2):
    # 虚拟哨兵节点
    dummy = Node(-1)
    cur = dummy
    while head_1 and head_2:
        if head_1.val <= head_2.val:
            cur.next = head_1
            head_1 = head_1.next
        else:
            cur.next = head_2
            head_2 = head_2.next
        cur = cur.next
    # 拼接剩余节点
    cur.next = head_1 if head_1 else head_2
    return dummy.next

测试用例验证 #

你给出的测试用例运行后，合并后的链表顺序为：5 → 6 → 7 → 8 → 9 → 10 → 12 → 20 → 25 → 28，可以通过如下代码打印验证：

def print_list(head):
    res = []
    while head:
        res.append(str(head.val))
        head = head.next
    print(" -> ".join(res))

# 测试用例构造代码
a = Node(5)
b = Node(7)
c = Node(10)
d = Node(12)
e = Node(20)
f = Node(28)
a.next = b
b.next = c
c.next = d
d.next = e
e.next = f

q = Node(6)
r = Node(8)
s = Node(9)
t = Node(25)
q.next = r
r.next = s
s.next = t

merged_head = merge_lists(a, q)
print_list(merged_head)

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