Python实现合并两个有序链表的迭代与递归详解

夏知夏

发布时间：2026-10-13 | 6人浏览过

原创

本文详细介绍Python中合并两个单调递增链表的两种核心方法：迭代与递归。通过对比代码实现，解析迭代法中指针移动的逻辑以及递归法中状态转移与边界条件的处理。文章还总结了递归算法设计的三个关键步骤，帮助开发者理解函数式编程思想在链表操作中的应用，并提供完整可运行的代码示例供参考。

给定两个单调递增的链表，要求将它们合并为一个新的链表，并确保新链表依然保持单调不减的顺序。

第一种实现方式采用迭代策略。

  def Merge(self, pHead1, pHead2):
    p1, p2 = pHead1, pHead2
    if p1 and p2:
      if p1.val < p2.val:
        head = p1
        p1 = p1.next
      else:
        head = p2
        p2 = p2.next
      cur = head
    elif p1:
      return p1
    else:
      return p2

    while p1 and p2:
      if p1.val < p2.val:
        cur.next = p1
        p1 = p1.next
      else:
        cur.next = p2
        p2 = p2.next
      cur = cur.next
    if p1:
      cur.next = p1
    else:
      cur.next = p2
    return head

第二种实现方式采用递归策略。

  def Merge_rcv(self, pHead1, pHead2):
    if not pHead1:
      return pHead2
    if not pHead2:
      return pHead1
    if pHead1.val < pHead2.val:
      pres = pHead1
      pres.next = self.Merge(pHead1.next, pHead2)
    else:
      pres = pHead2
      pres.next = self.Merge(pHead1, pHead2.next)
    return pres

补充说明：

递归算法的运行逻辑看似复杂，但其代码结构通常非常简洁。每一层递归调用都清晰地表达了“当前节点需要执行的操作”。

在构思递归算法时，建议遵循以下步骤：

1) 确定每一层递归需要完成的具体任务，例如：比较两个链表当前节点的值，选择较小的那个作为当前合并链表的节点。

2) 确定任务的结束点以及递归调用的连接点，例如：在 `pres.next` 处发起下一层递归调用。

3) 明确递归终止条件，例如：当 `p1` 或 `p2` 中任意一个链表遍历完毕（为空）时，递归任务结束，直接返回剩余的非空链表部分。

绝大多数递归算法都可以依据上述三个要素进行构建。只要能在脑海中清晰回答这三个问题，并稍加修饰代码，就能写出完整的递归算法。

这也体现了函数式编程中关注点分离和状态转移的魅力。

以上关于Python实现合并两个排序链表的详细解析到此结束，希望能为读者提供有价值的参考。如果您觉得内容有帮助，欢迎支持本站。