/*
 * [21] 合并两个有序链表
 */

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function (list1, list2) {
  // 1. 简单的方法
  const ans = new ListNode()
  let prev = ans;
  while (list1 && list2) {
    if (list1.val >= list2.val) {
      prev.next = list2;
      list2 = list2.next;
    } else {
      prev.next = list1;
      list1 = list1.next;
    }
    prev = prev.next;
  }

  prev.next = list1 === null ? list2 : list1;
  return ans.next;

  // 2. 复杂的方法
  // let ans = new ListNode()
  // let c1 = list1
  // let c2 = list2
  // let temp = ans;
  // while (c1 && c2) {
  //   if (c1.val <= c2.val) {
  //     temp.next = c1
  //     c1 = c1.next
  //   } else {
  //     temp.next = c2
  //     c2 = c2.next
  //   }
  //   temp = temp.next
  // }

  // while (c1) {
  //   temp.next = c1
  //   c1 = c1.next
  //   temp = temp.next
  // }
  // while (c2) {
  //   temp.next = c2
  //   c2 = c2.next
  //   temp = temp.next
  // }
  // return ans.next
};

function ListNode(val, next) {
  this.val = val || 0
  this.next = next || null
}

const n1 = new ListNode(1)
const n2 = new ListNode(2)
const n4 = new ListNode(4)

n1.next = n2
n2.next = n4


const m1 = new ListNode(1)
const m2 = new ListNode(3)
const m4 = new ListNode(4)
m1.next = m2
m2.next = m4

console.log(n1)
console.log(m1)
console.log(mergeTwoLists(n1, m1))