[21] 合并两个有序链表

思路

可以列举如下两个链表：

// 1 -> 3 -> 5 -> 7 -> 9
// 2 -> 4 -> 6 -> 8 -> 10

定义一个新的链表头，这个头节点可以缓存最终的结果，再定义一个指针，初始时指向头节点：

let head = new ListNode();
let curr = head;

再定义两个指针，利用这两个指针分别对list1和list2进行迭代：

// 根据开头的两个例子，可以看成，在初始时，curr_1就是第一个链表的1
let curr_1 = list1;
// curr_2就是第二个链表的2
let curr_2 = list2;

此时，要对两个链表进行合并，则需要对两个链表同时迭代：

while (curr_1 !== null && curr_2 !== null) {
  // 都不为null时才进入遍历
  if (curr_1.val < curr_2.val) {
    // 如果链表1的当前值更小，那新头的指针curr.next就指向它
    curr.next = curr_1;
    // 此时较小值已被指向，所以就取下一个，而当前遍历到的较大值不变
    // 进入下一次遍历的对比
    curr_1 = curr_1.next;
  } else {
    // 同理
    curr.next = curr_2;
    curr_2 = curr_2.next;
  }
  curr = curr.next;
}

两个链表的长度不一定相等，所以最终可能会剩余一截链表，如果还剩了，那么肯定直接指向剩下的那一截链表的头：

curr.next = curr_1 === null ? curr_2 : curr_1;

最终结果

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
  if (list1 === null && list2 === null) return null;
  if (list1 === null || list2 === null) return list1 || list2;
  // 这个头节点用来保存结果，首先根据题干，假设结果为最小极限值
  let head = new ListNode();
  // 这个是指针，用来指向head中的当前节点
  let curr = head;
  let curr_1 = list1;
  let curr_2 = list2;
  while (curr_1 !== null && curr_2 !== null) {
    // 都不为null时才进入遍历
    if (curr_1.val < curr_2.val) {
      curr.next = curr_1;
      curr_1 = curr_1.next;
    } else {
      curr.next = curr_2;
      curr_2 = curr_2.next;
    }
    curr = curr.next;
  }
  // 如果有一截还剩着
  curr.next = curr_1 === null ? curr_2 : curr_1;
  return head.next;
}