链表题目:合并两个有序链表

文章目录

题目

标题和出处

标题:合并两个有序链表

出处:21. 合并两个有序链表

难度

3 级

题目描述

要求

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的。

示例

示例 1:

链表题目:合并两个有序链表

输入: l1   =   [1,2,4],   l2   =   [1,3,4] \texttt{l1 = [1,2,4], l2 = [1,3,4]} l1 = [1,2,4], l2 = [1,3,4]
输出: [1,1,2,3,4,4] \texttt{[1,1,2,3,4,4]} [1,1,2,3,4,4]

示例 2:

输入: l1   =   [],   l2   =   [] \texttt{l1 = [], l2 = []} l1 = [], l2 = []
输出: [] \texttt{[]} []

示例 3:

输入: l1   =   [],   l2   =   [0] \texttt{l1 = [], l2 = [0]} l1 = [], l2 = [0]
输出: [0] \texttt{[0]} [0]

数据范围

  • 两个链表的结点数目范围是 [0,   50] \texttt{[0, 50]} [0, 50]
  • -100 ≤ Node.val ≤ 100 \texttt{-100} \le \texttt{Node.val} \le \texttt{100} -100≤Node.val≤100
  • l1 \texttt{l1} l1 和 l2 \texttt{l2} l2 均按非递减顺序排列

解法一

思路和算法

如果两个链表都为空,则合并后的链表也为空。如果两个链表中有一个链表为空,则合并后的链表为另一个链表。这两种情况可以概括为:分别判断两个链表是否为空,如果其中一个链表为空,则返回另一个链表作为合并后的结果。

如果两个链表都不为空,则为了满足合并后的链表有序,合并后的链表的头结点应为两个链表的头结点中的值较小的结点,确定头结点之后,再对剩下的结点进行合并。

对于链表 l l l,用 l [ 0 ] l[0] l[0] 表示其头结点, l [ 1 : ] l[1:] l[1:] 表示除了头结点以外的部分,则合并操作可以表示成如下形式:

mergeTwoLists ( l 1 , l 2 ) = { l 1 [ 0 ] + mergeTwoLists ( l 1 [ 1 : ] , l 2 ) , l 1 [ 0 ] . val ≤ l 2 [ 0 ] . val l 2 [ 0 ] + mergeTwoLists ( l 1 , l 2 [ 1 : ] ) , l 1 [ 0 ] . val > l 2 [ 0 ] . val \text{mergeTwoLists}(l_1, l_2) = \begin{cases} l_1[0] + \text{mergeTwoLists}(l_1[1:], l_2), & l_1[0].\textit{val} \le l_2[0].\textit{val} \\ l_2[0] + \text{mergeTwoLists}(l_1, l_2[1:]), & l_1[0].\textit{val} > l_2[0].\textit{val} \end{cases} mergeTwoLists(l1​,l2​)={l1​[0]+mergeTwoLists(l1​[1:],l2​),l2​[0]+mergeTwoLists(l1​,l2​[1:]),​l1​[0].val≤l2​[0].vall1​[0].val>l2​[0].val​

根据上述表示形式,合并操作是一个递归的过程。

递归的终止条件是两个链表中至少有一个链表为空,如果其中一个链表为空,则返回另一个链表作为合并后的结果。

如果两个链表都不为空,则可以调用上述递归完成链表的合并。

代码

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else {
            if (l1.val <= l2.val) {
                l1.next = mergeTwoLists(l1.next, l2);
                return l1;
            } else {
                l2.next = mergeTwoLists(l1, l2.next);
                return l2;
            }
        }
    }
}

复杂度分析

  • 时间复杂度: O ( m + n ) O(m + n) O(m+n),其中 m m m 和 n n n 分别是两个链表的长度。合并过程中最多需要遍历两个链表中的每个结点一次。

  • 空间复杂度: O ( m + n ) O(m + n) O(m+n),其中 m m m 和 n n n 分别是两个链表的长度。空间复杂度主要取决于递归调用栈的深度,递归调用栈最多不会超过 m + n m + n m+n 层。

解法二

思路和算法

也可以使用迭代的方法合并链表。当两个链表都不为空时,比较两个链表的对应结点值,将值较小的结点合并到结果链表中,然后将对应链表的结点向后移动一步。如果一个链表为空,或者遍历完毕,则将另一个链表的剩下的部分合并到结果链表中。

由于合并后的链表的头结点需要通过比较两个链表的头结点决定,因此需要创建哑结点 dummyHead \textit{dummyHead} dummyHead,将合并的结点依次添加到哑结点的后面。具体做法是,创建指针 temp \textit{temp} temp 表示上一个合并的结点,初始时 temp \textit{temp} temp 指向 dummyHead \textit{dummyHead} dummyHead,每次合并结点时,将合并的结点添加到 temp \textit{temp} temp 的后面,然后将 temp \textit{temp} temp 向后移动一步,直到合并完毕。合并结束之后, dummyHead . next \textit{dummyHead}.\textit{next} dummyHead.next 即为合并后的新链表的头结点。

下图为一个迭代合并链表的例子。灰色表示哑结点,黄色表示两个链表中遍历到的结点,绿色表示 temp \textit{temp} temp 指向的结点。

链表题目:合并两个有序链表

代码

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode temp = dummyHead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                temp.next = l1;
                l1 = l1.next;
            } else {
                temp.next = l2;
                l2 = l2.next;
            }
            temp = temp.next;
        }
        if (l1 != null) {
            temp.next = l1;
        } else {
            temp.next = l2;
        }
        return dummyHead.next;
    }
}

复杂度分析

  • 时间复杂度: O ( m + n ) O(m + n) O(m+n),其中 m m m 和 n n n 分别是两个链表的长度。合并过程中最多需要遍历两个链表中的每个结点一次。

  • 空间复杂度: O ( 1 ) O(1) O(1)。

上一篇:node.js的koa@2性能测试


下一篇:nodejs中执行Shell命令(koa+vue)