【LeetCode 热题 100】21. 合并两个有序链表——（解法二）递归法（【LeetCode 热题 100】21. 递归解法：有序链表合并）
情感透析
2025年07月10日 15:10 19
aaron
标题：【LeetCode 热题 100】21. 合并两个有序链表——（解法二）递归法
一、引言
LeetCode 热题 100 中的第 21 题是“合并两个有序链表”，这是一个经典的链表操作问题。在这里，我们将介绍如何使用递归法来解决这个题目。这种 *** 适合初学者和进阶用户。
二、解题思路
递归法的基本思想是将问题分解为更小的子问题，然后逐步解决这些子问题。对于合并两个有序链表，我们可以将问题分解为合并链表的头部和剩余部分。
三、具体步骤
定义链表节点结构
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
编写递归函数
def mergeTwoLists(l1, l2):
# 如果一个链表为空，直接返回另一个链表
if not l1:
return l2
if not l2:
return l1
# 比较两个链表的头部，将较小的节点放在结果链表的头部
if l1.val < l2.val:
l1.next = mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = mergeTwoLists(l1, l2.next)
return l2
创建测试用例
# 创建两个有序链表
l1 = ListNode(1, ListNode(2, ListNode(4)))
l2 = ListNode(1, ListNode(3, ListNode(4)))
# 合并链表
merged_list = mergeTwoLists(l1, l2)
遍历合并后的链表
while merged_list:
print(merged_list.val, end=' ')
merged_list = merged_list.next
四、总结
通过递归法合并两个有序链表，我们可以将复杂的问题分解为简单的子问题，并逐步解决。这种 *** 有助于我们理解递归的基本原理，同时也能够提高我们的编程能力。
五、适用人群
本文适合初学者和进阶用户阅读，通过学习递归法合并有序链表，读者可以加深对递归概念的理解，并提升链表操作技能。
最新评论