Python递归实现：将两个有序单链表合并排序

可以通过递归的方式将两个有序的单链表合并为一个有序的单链表。 首先，定义一个ListNode类表示单链表的节点： ```python class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next ``` 然后，定义一个mergeTwoLists函数，用于合并两个有序的单链表： ```python def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode: # 如果其中一个链表为空，直接返回另一个链表即可 if not l1: return l2 if not l2: return l1 # 选择头节点较小的链表作为合并后的链表 if l1.val <= l2.val: merged_head = l1 merged_head.next = mergeTwoLists(l1.next, l2) else: merged_head = l2 merged_head.next = mergeTwoLists(l1, l2.next) return merged_head ``` 接下来，可以创建两个有序的单链表，并调用mergeTwoLists函数进行合并排序： ```python # 创建第一个有序链表：1 -> 3 -> 5 l1 = ListNode(1) l1.next = ListNode(3) l1.next.next = ListNode(5) # 创建第二个有序链表：2 -> 4 -> 6 l2 = ListNode(2) l2.next = ListNode(4) l2.next.next = ListNode(6) # 合并排序两个链表 merged_list = mergeTwoLists(l1, l2) # 打印合并后的链表：1 -> 2 -> 3 -> 4 -> 5 -> 6 while merged_list: print(merged_list.val, end=" -> ") merged_list = merged_list.next print("None") ``` 输出结果为：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None，表示两个有序链表合并排序后的结果。 ######[AI写代码神器 | 899点数解答 | 2024-06-04 16:32:06]