网络异常,图片无法展示
|
题目地址(25. 合并两个排序的链表)
题目描述
输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。 示例1: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 限制: 0 <= 链表长度 <= 1000 注意:本题与主站 21 题相同:https://leetcode-cn.com/problems/merge-two-sorted-lists/
思路
递归实现
代码
- 语言支持:Python3
Python3 Code:
# 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: #递归 if l1 == None : return l2 if l2 == None : return l1 if l1.val <= l2.val: l1.next = self.mergeTwoLists(l1.next, l2) return l1 else: l2.next = self.mergeTwoLists(l1, l2.next) return l2
复杂度分析
令 n 为数组长度。
- 时间复杂度:O(n)O(n)
- 空间复杂度:O(n)O(n)