21. 合并两个有序链表

21. 合并两个有序链表

迭代

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
  if (!list1) {
    return list2
  }

  if (!list2) {
    return list1
  }

  // 记录下来当前的值和上一个结点的值，然后往中间插入

  // 使用两个指针指向当前遍历到的链表的位置
  // 每次都将更小的值插入结果末尾
  // 最终就是有序的

  // 新建一个结点，这样无论哪个链表是开头
  // 最终结果都是 dummyHead.next 为开头
  const dummyHead = new ListNode()

  let p = dummyHead // 结果链表的末尾结点
  let p1 = list1 // 第一个链表当前遍历到的结点
  let p2 = list2  // 第二个链表当前遍历到的结点

  // 每次将两个指针所在的结点进行比较
  // 将更小的接到 dummyHead 的 p 的末尾
  while (p1 && p2) {
    if (p1.val < p2.val) {
      p.next = p1

      p1 = p1.next
    } else {
      p.next = p2

      p2 = p2.next
    }

    p = p.next
  }

  // 剩下的没有处理的要么是 p1，要么是 p2
  // 直接放在 p 的末尾即可
  if (p1) {
    p.next = p1
  } else {
    p.next = p2
  }

  return dummyHead.next
}

递归

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
  if (!list1) {
    return list2
  }

  if (!list2) {
    return list1
  }

  // 对于两个链表合并来说
  // 相当于将一个结点和下一个结点与另一个链表合并
  // 所以可以递归解决

  // 如果 list1 比 list2 小
  // 要合并的是 list1 + (list1.next, list2)
  if (list1.val < list2.val) {
    // 将 list1.next 指向合并结果
    list1.next = mergeTwoLists(list1.next, list2)

    return list1
  } else {
    // 要合并的是 list2 + (list2.next, list1)
    // 将 list1.next 指向合并结果
    list2.next = mergeTwoLists(list2.next, list1)

    return list2
  }

  return mergeTwoLists(list1, list2)
}