美文网首页
剑指 offer 25. 合并两个排序的链表

剑指 offer 25. 合并两个排序的链表

作者: Sun东辉 | 来源:发表于2022-06-27 19:41 被阅读0次

输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1:

输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4

限制:

  • 0 <= 链表长度 <= 1000

解题思路:递归

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }
    if l1.Val > l2.Val {
        l1, l2 = l2, l1
    }
    l1.Next = mergeTwoLists(l1.Next, l2)
    return l1
}
  • 时间复杂度:O(m+n),其中 m 和 n 分别为两个链表的长度。因为每次递归都会去掉 l2 或 l1 的头节点,直到其中一个链表为空,因此,时间复杂度取决于合并后链表的长度,即 O(m+n)
  • 空间复杂度:O(m+n),其中 m 和 n 分别为两个链表的长度。递归调用消耗的栈空间大小取决于递归调用的深度,递归执行次数为 m+n,因此,空间复杂度为 O(m+n)

相关文章

网友评论

      本文标题:剑指 offer 25. 合并两个排序的链表

      本文链接:https://www.haomeiwen.com/subject/efjovrtx.html