将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/merge-two-sorted-lists 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
递归解法
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: # 如果l1或l2有一个为空,则直接返回不为空的那个 if l1 and l2: # 如果l1比l2大,将l1,l2值互换,使得 l1 指向比较小的那个节点对象 if l1.val > l2.val: l1, l2 = l2, l1 # 修改 l1 的 next 属性为递归函数返回值 l1.next = self.mergeTwoLists(l1.next, l2) return l1 or l2