21、合并两个有序链表

;(function () {
  /**
   * 21. 合并两个有序链表
   * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
   *
   * 输入：list1 = [1,2,4], l2 = [1,3,4]
   * 输出：[1,1,2,3,4,4]
   *
   */

  /**
   * 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(
    list1: ListNode | null,
    list2: ListNode | null
  ): ListNode | null {
    // 方法一: 官方
    if (list1 === null) {
      return list2
    } else if (list2 === null) {
      return list1
    } else if (list1.val < list2.val) {
      list1.next = mergeTwoLists(list1.next, list2)
      return list1
    } else {
      list2.next = mergeTwoLists(list1, list2.next)
      return list2
    }

    // 方法二： 迭代（官方）
    // const  prehead = new ListNode(-1);
    // let prev = prehead;
    // while(list1 !== null && list2 !== null) {
    //     if (list1.val < list2.val) {
    //         prev.next = list1;
    //         list1 = list1.next;
    //     } else {
    //         prev.next = list2;
    //         list2 = list2.next;
    //     }
    //     prev = prev.next;
    // }
    // prev.next = list1 === null ? list2 : list1;
    // return prehead.next
  }
})()