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

橘子海

发布时间：2026-10-11| 2人浏览过

原创

本文介绍如何使用 Python 合并两个单调递增的链表，生成一个新的单调不减链表。文章详细解析了非递归（迭代）和递归两种实现思路，提供了完整的代码示例及测试用例，帮助开发者理解指针操作与递归逻辑在链表处理中的应用。

问题描述

给定两个单调递增的链表，要求将它们合并为一个新的单调不减链表。输入为两个链表的头节点，输出为合并后链表的头节点。

非递归实现（迭代法）

迭代法的核心在于维护一个“主链表”和一个“次链表”，并通过指针操作将次链表的节点逐个插入到主链表中。

算法步骤

确定主链表与次链表：比较两个链表头节点的值，值较小的链表作为主链表（mainHead），另一个作为次链表（secHead）。主链表的头节点即为最终合并链表的头节点（mergeHead）。
初始化指针：定义两个指针，mainHead 指向主链表的当前节点，mainNext 指向主链表的下一个节点（mainHead.next）。
遍历与插入：当 mainNext 和 secHead 均不为空时，进行循环：

若 secHead.val <= mainNext.val，说明次链表的当前节点应插入到主链表当前节点与下一个节点之间。执行以下操作：
- 将 mainHead.next 指向 secHead。
- 更新 secHead 指向其下一个节点。
- 将新插入节点的 next 指向 mainNext。
- 将 mainHead 移动到刚插入的节点。
否则，说明主链表的当前顺序正确，只需将 mainHead 和 mainNext 同时后移。

处理剩余节点：若主链表遍历完毕（mainNext 为空），将主链表尾部指向次链表的剩余部分。
返回结果：返回 mergeHead。

代码实现

def Merge(self, pHead1, pHead2):
    if not pHead1:
        return pHead2
    if not pHead2:
        return pHead1
    
    # 确定主链表和次链表
    mainHead = pHead1 if pHead1.val <= pHead2.val else pHead2
    secHead = pHead2 if mainHead == pHead1 else pHead1
    mergeHead = mainHead
    
    # 主链表的下一个节点指针
    mainNext = mainHead.next
    
    while mainNext and secHead:
        if secHead.val <= mainNext.val:
            # 插入次链表节点到主链表
            mainHead.next = secHead
            secHead = secHead.next
            mainHead.next.next = mainNext
            mainHead = mainHead.next
        else:
            # 主链表指针后移
            mainHead = mainNext
            mainNext = mainNext.next
            
    # 如果主链表遍历完，连接次链表剩余部分
    if not mainNext:
        mainHead.next = secHead
        
    return mergeHead

递归实现

递归版本的代码逻辑更为清晰，通过不断比较头节点值，将较小节点的 next 指向剩余部分的合并结果。

算法步骤

基准情况：若其中一个链表为空，直接返回另一个链表的头节点。
比较头节点：比较 pHead1 和 pHead2 的值。
递归调用：
- 若 pHead1.val <= pHead2.val，则 pHead1.next 指向 Merge(pHead1.next, pHead2) 的结果，并返回 pHead1。
- 否则，pHead2.next 指向 Merge(pHead1, pHead2.next) 的结果，并返回 pHead2。

代码实现

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

完整测试代码

为了验证上述算法，以下提供了包含链表节点定义、辅助函数以及测试用例的完整 Python 代码。

class Solution:

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

    def getNewChart(self, list):
        """辅助函数：将列表转换为链表"""
        if list:
            node = ListNode(list.pop(0))
            node.next = self.getNewChart(list)
            return node

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

if __name__ == '__main__':
    # 测试用例
    list1 = [1, 3, 5]
    list2 = [0, 1, 4]
    
    # 创建链表
    testList1 = Solution().getNewChart(list1)
    testList2 = Solution().getNewChart(list2)
    
    # 合并链表
    final = Solution().Merge(testList1, testList2)
    
    # 打印结果
    while final:
        print(final.val, end=" ")
        final = final.next