解题步骤

  1. 新建一个新链表，作为返回结果
  2. 用指针遍历两个有序链表，并比较两个链表的当前节点，较小者先接入新链表，并将指针后移一步
  3. 链表遍历结束，返回新链表

通过链表的方式实现

  • 时间复杂度：O (m + n)

  • 空间复杂度：O (1)

    1. function mergeTwoLists(list1, list2) {
    2.   const res = new ListNode(0);
    4.   let p = res;
    5.   let p1 = list1;
    6.   let p2 = list2;
    8.   while (p1 && p2) {
    9.       if (p1.val < p2.val) {
    10.           p.next = p1;
    11.           p1 = p1.next;
    12.       } else {
    13.           p.next = p2;
    14.           p2 = p2.next;
    15.       }
    17.       p = p.next;
    18.   }
    20.   if (p1) {
    21.       p.next = p1;
    22.   }
    23.   if (p2) {
    24.       p.next = p2;
    25.   }
    27.   return res.next;
    28. }

代码中主要遍历了 list1 和 list2 ，所以时间复杂度是 O (m + n)，而空间复杂度是 O (1)，因为我们新建的变量都是一些指针，不是数组也不是矩阵，所以是不会随着数据增大而增大。