21.合并两个有序链表.md

21.合并两个有序链表

/*
 * @lc app=leetcode.cn id=21 lang=typescript
 *
 * [21] 合并两个有序链表
 */

// @lc code=start
/**
 * 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(l1: ListNode | null, l2: ListNode | null): ListNode | null {}
// @lc code=end

解法 1: 双指针

• 将 small 指向两个链表中当前结点较小的结点,large 指向较大的结点
• 每次迭代,如果 small.next 大于 large,则需要将 small.nxet 指向 large,并将 small 和 large 重新指向 large 和原 small.next,因为 small.next 会被覆盖,所以一定要用另外一个变量先存起来
• 如果 small.next 小于或等于 large,则只需要将 small 指向 small.next 即可
• 如果 small.next 不存在,则已经到最后一个结点,则只要将 small.next 指向 large 即可,并返回 root

function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  if (!l1 || !l2) return l1 ? l1 : l2

  let [small, large] = [l1, l2]
  if (l1.val > l2.val) [small, large] = [large, small]
  const root = small

  while (true) {
    if (small.next) {
      const next = small.next
      if (next.val > large.val) {
        small.next = large
        ;[small, large] = [large, next]
      } else {
        small = next
      }
    } else {
      small.next = large
      return root
    }
  }
}

解法 2: 递归

TODO