Python递归实现：合并排序两个单链表，附代码详解

可以使用递归或迭代的方法来实现合并排序两个单链表。下面是使用递归的方法实现： ```python class ListNode: def __init__(self, value=0, next=None): self.value = value self.next = next def merge(l1: ListNode, l2: ListNode) -> ListNode: if not l1: return l2 if not l2: return l1 if l1.value <= l2.value: l1.next = merge(l1.next, l2) return l1 else: l2.next = merge(l1, l2.next) return l2 # 测试 # 创建链表1: 1->3->5 l1 = ListNode(1) l1.next = ListNode(3) l1.next.next = ListNode(5) # 创建链表2: 2->4->6 l2 = ListNode(2) l2.next = ListNode(4) l2.next.next = ListNode(6) merged_list = merge(l1, l2) # 输出合并后的链表: 1->2->3->4->5->6 while merged_list: print(merged_list.value, end=" ") merged_list = merged_list.next ``` 输出结果: ``` 1 2 3 4 5 6 ``` 以上代码首先定义了链表节点`ListNode`类，其中包含一个值属性`value`和指向下一个节点的指针`next`。然后，定义了`merge`函数，利用递归的方式合并两个链表。函数首先检查是否有一个链表为空，如果是，则直接返回另一个链表。然后，比较两个链表的第一个节点的值，将较小的节点作为合并后的链表的头节点，并递归调用`merge`函数合并剩余的部分。创建两个测试链表，并调用`merge`函数得到合并后的链表，然后遍历输出合并后的链表的值。 ######[AI写代码神器 | 848点数解答 | 2024-06-04 16:16:40]