题解:
这段代码是用于合并两个有序列表的递归函数,函数的输入是两个链表l1和l2,返回合并后的有序列表。具体操作是比较两个链表的头结点,将较小的头结点作为合并后的链表的头结点,并递归的将剩余的部分与另一个链表进行合并,如一个链表为空,则直接返回另一个链表。
这段代码主要逻辑是比较两个链表的头结点值,然后递归地处理剩余的部分。
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
# 如果l1为空,直接返回l2
if not l1:
return l2
# 如果l2为空,直接返回l1
if not l2:
return l1
# 比较l1和l2的头结点的值,将较小的头结点作为合并后链表的头结点
if l1.val <= l2.val:
# 递归地将l1的下一个节点与l2合并,并将结果赋给l1的下一个节点
l1.next = self.mergeTwoLists(l1.next, l2)
# 返回合并后的链表
return l1
else:
# 递归地将l1与l2的下一个节点合并,并将结果赋给l2的下一个节点
l2.next = self.mergeTwoLists(l1, l2.next)
# 返回合并后的链表
return l2
代码通过递归的方式,将两个有序链表合并为一个有序链表,递归的终止条件是其中一个链表为空,此时直接返回另一个链表。递归的过程中,每次比较两个链表的头结点的值,将较小的头结点作为合并后的链表的当前结点,然后递归的处理剩余部分,直至两个链表都为空。
可以进行一些微小的优化,例如通过迭代来替换递归,避免函数调用的开销。以下是一个迭代版本的优化:
这个优化版本使用迭代而不是递归来合并链表,避免了函数调用的开销,但逻辑和之前的代码是一样的。
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
# 创建一个哑节点作为合并后链表的头节点
dummy = ListNode(-1)
# 创建一个指针指向合并后链表的当前节点,初始指向哑节点
current = dummy
# 循环直到l1和l2中有一个为空
while l1 and l2:
# 比较l1和l2的头结点的值,将较小的头结点接在当前节点的后面
if l1.val <= l2.val:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
# 移动当前节点指针到新的尾节点
current = current.next
# 将剩余部分(如果有)接在合并后链表的尾部
current.next = l1 if l1 else l2
# 返回合并后链表的头节点(去掉哑节点)
return dummy.next