21.合并两个有序链表

题目描述 (opens new window)

TIP

标签：递归、链表

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

示例1:

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例2:

输入：l1 = [], l2 = []
输出：[]

示例3:

输入：l1 = [], l2 = [0]
输出：[0]

方法一：迭代法：

思路: 注意题目中给定的要求，是拼接两个链表中的所有节点。要考虑的边界条件是链表节点为空的场景。

我们可以使用迭代的方法实现上述算法，当l1和l2都不是空链表时，判断l1和l2哪一个链表的头节点值更小，将较小的节点添加到结果中去，当一个节点被添加到结果中之后，将对应链表中的节点向后移动一位。

算法: 首先，我们设定一个虚拟节点，这样可以在最后让我们比较容易的返回新合成的链表，我们维护一个cur指针，我们需要做的就是调整它的next指针，然后，我们重复以下过程，直到l1或者l2指向了null。

• 如果 l1 当前节点的值小于等于 l2 ，我们就把 l1 当前的节点接在 cur 节点的后面同时将 l1 指针往后移一位。
• 否则，我们对 l2 做同样的操作。不管我们将哪一个元素接在了后面，我们都需要把 cur 向后移一位。

在循环终止的时候， l1 和 l2 至多有一个是非空的。由于输入的两个链表都是有序的，所以不管哪个链表是非空的，它包含的所有元素都比前面已经合并链表中的所有元素都要大。这意味着我们只需要简单地将非空链表接在合并链表的后面，并返回合并链表即可。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function (l1, l2) {
  // 创建一个新的链表的头节点
  let newHead = new ListNode(-1);
  let cur = newHead; // 将head节点赋值给 cur 之后cur 方便移动
  // 因为在内部的循环中,会频繁的使用l1.next 和 l2.next 所以为了防止空指针
  // 这里需要做防空处理
  while (l1 !== null && l2 !== null) {
    if (l1.val < l2.val) {
      cur.next = l1;
      l1 = l1.next
    } else {
      cur.next = l2;
      l2 = l2.next;
    }
    cur = cur.next;
  }
  cur.next = l1 || l2;
  return newHead.next;
};

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
  let dummyHead = new ListNode(-1);
  let cur = dummyHead;

  while (list1 !== null && list2 !== null) {
    if (list1.val < list2.val) {
      cur.next = list1;
      list1 = list1.next;
    } else {
      cur.next = list2;
      list2 = list2.next
    }
    cur = cur.next
  }
  // while循环的条件是两个都不为空 退出循环时候肯定有一个为空
  cur.next = list1 || list2;
  return dummyHead.next
};

链表的题目，对于迭代方法来说，一个虚拟头结点的创建非常必要，这已经算是一种解题技巧了，为了不判断空节点的情况，循环的条件设置为两个非空的形式，在循环条件结束的时候再判断这种情况。

复杂度分析:

• 时间复杂度：O(n + m), 其中 n 和 m 分别为两个链表的长度。因为每次循环迭代中，l1 和 l2 只有一个元素会被放进合并链表中， 因此 while 循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的，因此总的时间复杂度为 O(n+m)
• 空间复杂度：O(1)。我们只需要常数的空间存放若干变量。