算法-合并两个有序链表

第四天

题目

合并两个有序链表

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

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

原题传送门

思考

和昨日的链表部分思路是一致的，使用指针定位节点并比较

划掉！用个**指针！

递归，就直接递归！

根据题目获取条件

• 有序链表，我们可以逐个比较
• 递归内容: link.val 比较，小的一方作为链表头拼接到 res 后
• 递归终止条件: 两个链表长度不定，其中一个链表 next === null 后结束
• 递归返回值: 返回比较后的两个链表

function ListNode(val, next) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
}

function mergeTwoLists (l1, l2) {
  if (l1 === null) return l2
  if (l2 === null) return l1

  if (l1.val < l2.val) {
    l1.next = mergeTwoLists(l1.next, l2)

    return l1
  } else {
    l2.next = mergeTwoLists(l1, l2.next)

    return l2
  }
}

记住递归算法要找出三个要点：递归停止条件、递归内容、递归返回值