山西企业模板建站信息外贸移动端网站模板

合并两个有序链表

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

图一

示例 1：（如图一）
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]示例 2：
输入：l1 = [], l2 = []
输出：[]示例 3：
输入：l1 = [], l2 = [0]
输出：[0]

我的思路
昨天没搞清楚，今天先来看看什么是链表：
链表是由数据+指针构造而成的，指针指向下一个节点的地址。如下图：

所以在定义 ListNode 结构的时候，就需要定义两个属性，一个是当前节点的值，一个是指向下一个节点地址，用来实现指针的功能。

网上思路
递归

我的思路

var mergeTwoLists = function (list1, list2) {const dummy = new ListNode(0);let current = dummy;while (list1 !== null && list2 !== null) {if (list1.val < list2.val) {current.next = list1;list1 = list1.next;} else {current.next = list2;list2 = list2.next;}current = current.next;}if (list1 !== null) {current.next = list1;} else if (list2 !== null) {current.next = list2;}return dummy.next;
}

讲解
思路：

1. 创建一个虚拟头节点 dummy，用于简化链表操作。
2. 使用 current 指针指向当前合并链表的末尾。
3. 使用 while 循环遍历两个链表，比较当前节点的值，将较小的节点加入到新链表中。
4. 当一个链表遍历完后，将另一个链表的剩余部分连接到新链表的末尾。
5. 最后返回合并后的链表，跳过虚拟头节点。

网上思路

var mergeTwoLists = function(l1, l2) {if (l1 === null) {return l2;} else if (l2 === null) {return l1;} else if (l1.val < l2.val) {l1.next = mergeTwoLists(l1.next, l2);return l1;} else {l2.next = mergeTwoLists(l1, l2.next);return l2;}
};作者：力扣官方题解
链接：https://leetcode.cn/problems/merge-two-sorted-lists/solutions/226408/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

讲解
这是力扣官网的解法

总结

正常的会了，但是递归的还没看太懂，回头继续学习。