1. 合并有序链表

LeetCode 第 21 题合并两个有序链表

题目

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

示例 1：

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

输出：[1,1,2,3,4,4]

示例 2：

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

输出：[]

示例 3：

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

输出：[0]

提示：两个链表的节点数目范围是 [0, 50] -100 <= Node.val <= 100 l1 和 l2 均按 非递减顺序排列

题目解析

两个链表都是有序的，那么只需要一次比较表头的数据，较小的赋值到新链表上，然后 next，较大的不动即可

/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function (list1, list2) {
  // 迭代指针
  let p1 = list1;
  let p2 = list2;
  // 新节点设置虚拟头节点
  let newList = {
    value: null,
    next: null,
  };
  // 新链表迭代指针
  let p3 = newList;
  // 如果两个链表都存在，开始迭代
  while (p1 && p2) {
    // 比较两个链表的值，取较小的值迭代，大的值不动
    if (p1.val < p2.val) {
      p3.next = p1;
      p1 = p1.next;
    } else {
      p3.next = p2;
      p2 = p2.next;
    }
    // 新链表向前迭代
    p3 = p3.next;
  }
  // 如果list 还剩余节点，那么 list2 不会有剩余，拼接剩余节点到后面即可
  if (p1) {
    p3.next = p1;
  }
  // 同上
  if (p2) {
    p3.next = p2;
  }
  // 返回新链表的头节点
  return newList.next;
};