简述已知两个链表head1 和head2 各自有序,请把它们合并成一个链表依然有序,这次要求用递归方法进行 ?
参考答案:
在Python中,您可以使用递归方法将两个已排序的链表合并成一个新的已排序链表。这里有一个示例:
首先,我们需要定义链表节点:
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
接下来,我们编写一个递归函数来合并两个链表:
def mergeTwoLists(l1, l2):
# 递归终止条件:当其中一个链表为空时,返回另一个链表
if l1 is None:
return l2
if l2 is None:
return l1
# 比较两个链表节点的值,将较小的节点添加到新链表中,然后递归调用合并剩余部分
if l1.val < l2.val:
l1.next = mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = mergeTwoLists(l1, l2.next)
return l2
这个递归函数首先检查两个链表的头节点。如果其中一个链表为空,它返回另一个链表。否则,它比较两个节点的值,并将较小的节点连接到新链表中。然后,它递归地调用自己来处理剩余的部分。
现在,假设我们有两个已排序的链表head1
和head2
,我们可以使用mergeTwoLists
函数将它们合并:
# 假设head1和head2是已排序链表的头节点
merged_head = mergeTwoLists(head1, head2)
合并后的链表merged_head
将是一个已排序的新链表。
这种方法的时间复杂度是O(n+m),其中n和m分别是两个链表的长度,因为每个节点都被访问一次。空间复杂度是O(1),因为除了存储指针之外,我们不需要额外的空间。