合并两个有序链表
坚持算法 第四天
题目#
合并两个有序链表
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入：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; }}记住递归算法要找出三个要点：递归停止条件、递归内容、递归返回值
