notes | Kisstar

# 合并两个有序链表

解题思路：

  1. 以其中一个链表为基准，开启外层循环遍历链表
  2. 内层循环遍历另一个链表，如果内循环的链表节点值小于外层循环的链表节点值，则将内循环的链表节点插入结果链表，并更新内循环链表指针
  3. 如果内循环的链表节点值大于外层循环的链表节点值，则将外层循环的链表节点插入结果链表，并更新外层循环链表指针
  4. 如果外循环遍历完，则将内层循环的链表节点插入结果链表，并结束循环（避免内存循环的值比较大而导致在内循环过程中没有添加到结果链表中）
var mergeTwoLists = function (list1, list2) {
  if (list1 === null) {
    return list2
  }
  if (list2 === null) {
    return list1
  }

  let p1 = list1,
    p2 = list2
  let ret // 结果链表的头指针
  let curr // 结果链表的当前指针

  // 判断链表1和链表2哪个节点值小，将哪个节点值小的节点作为结果链表的头指针
  if (p2.val < p1.val) {
    ret = { ...p2 }
    p2 = p2.next
  } else {
    ret = { ...p1 }
    p1 = p1.next
  }

  curr = ret

  // 外循环遍历链表1
  while (p1 && p1.val !== undefined) {
    // 内循环遍历链表2
    // 判断链表2的节点值是否小于等于链表1的节点值，如果小于等于则将链表2的节点插入结果链
    while (p2 && p2.val !== undefined && p2.val <= p1.val) {
      // 插入结果链表
      curr.next = p2
      // 更新结果链表指针
      curr = p2
      // 更新链表2指针
      p2 = p2.next
    }

    curr.next = p1
    curr = p1
    p1 = p1.next
  }

  // 判断链表2是否遍历完
  while (p2 && p2.val) {
    curr.next = p2
    curr = p2
    p2 = p2.next
  }

  return ret
}

同样的解题思路，官方提供了更简洁的写法：

var mergeTwoLists = function (l1, l2) {
  const prehead = new ListNode(-1)
  let prev = prehead

  while (l1 != null && l2 != null) {
    if (l1.val <= l2.val) {
      prev.next = l1
      l1 = l1.next
    } else {
      prev.next = l2
      l2 = l2.next
    }

    prev = prev.next
  }

  // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
  prev.next = l1 === null ? l2 : l1

  return prehead.next
}

# 参考

← 分隔链表 →