合并两个有序链表

LeetCode-21

两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的

// 也可遍历遍历两次放到一个数组里再排序，然后链接成链表
// 递归
var mergeTwoLists = function(list1, list2) {
  // 直到链表1为空 返回链表2
  if(list1 === null) return list2
  // 直到链表2为空 返回链表1
  if(list2 === null) return list1
  // 链表1节点值小于链表2节点值
  if(list1.val < list2.val) {
    // 说明list1的下一个节点为list1.next或list2；递归比较【相当于节点1往下走一个】
    list1.next = mergeTwoLists(list1.next, list2)
    return list1
  } else {
    // 链表1节点值大于链表2节点值
    // 说明list2的下一个节点为list2.next或list1；递归比较【相当于节点1往下走一个】
    list2.next = mergeTwoLists(list1, list2.next)
    return list2
  }
}