题目描述：
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
代码
/**
* 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) {
if(list1 === null) {
return list2;
}
if(list2 === null) {
return list1;
}
if(list1.val < list2.val) {
list1.next = mergeTwoLists(list1.next, list2);
return list1;
} else {
list2.next = mergeTwoLists(list2.next, list1);
return list2;
}
};
代码分析
这段代码是一个 JavaScript 函数，用于合并两个有序的单链表。下面是对代码的逐行解释：
-
首先，代码中定义了一个单链表节点
ListNode的构造函数。这个构造函数接收两个参数：val和next。val是节点的值，next是指向下一个节点的指针（在 JavaScript 中，指针通常是另一个节点对象或null表示链表的末尾）。function ListNode(val, next) { this.val = (val===undefined ? 0 : val) this.next = (next===undefined ? null : next) } -
接下来，定义了
mergeTwoLists函数，它接收两个参数：list1和list2。这两个参数是指向单链表头节点的指针。var mergeTwoLists = function(list1, list2) { // ... }; -
函数内部首先检查
list1是否为null。如果是，说明list1是一个空链表，因此直接返回list2。if(list1 === null) { return list2; } -
然后，检查
list2是否为null。如果是，说明list2是一个空链表，因此直接返回list1。if(list2 === null) { return list1; } -
如果两个链表都不为空，接下来比较
list1和list2的当前节点的值（val）。if(list1.val < list2.val) { // ... } else { // ... } -
如果
list1的当前节点值小于list2的当前节点值，将list1的next指针指向递归调用mergeTwoLists的结果，这个递归调用将合并list1的下一个节点和整个list2链表。然后，返回list1作为合并后链表的头节点。list1.next = mergeTwoLists(list1.next, list2); return list1; -
如果
list1的当前节点值大于或等于list2的当前节点值，将list2的next指针指向递归调用mergeTwoLists的结果，这个递归调用将合并list1和list2的下一个节点。然后，返回list2作为合并后链表的头节点。list2.next = mergeTwoLists(list1, list2.next); return list2; -
递归调用将持续进行，直到至少有一个链表为空。这时，非空链表将直接连接到递归调用返回的链表上，完成合并。
这个函数通过递归的方式，有效地合并了两个有序链表，保证了合并后的链表仍然是有序的。
案例分析：
让我们通过一个具体的例子来分析 mergeTwoLists 函数的执行过程。假设我们有两个有序链表：
list1: 1 -> 3 -> 5
list2: 2 -> 4 -> 6
下面是合并这两个链表的步骤：
-
初始化比较：首先，我们比较两个链表的头节点
list1（值为1）和list2（值为2）。因为1 < 2，我们选择list1的节点作为合并后链表的第一个节点。 -
递归调用：然后，我们将
list1的next指针指向mergeTwoLists的递归调用结果，这次调用的参数是list1.next（即值为3的节点）和list2。 -
继续比较：递归调用中，我们再次比较
list1.next（值为3）和list2。这次3 > 2，所以我们选择list2的节点作为合并链表的下一个节点。 -
递归调用 list2：
list2的next指针现在指向mergeTwoLists的另一个递归调用结果，参数是list1（值为1的节点）和list2.next（即值为4的节点）。 -
继续递归：在这次递归调用中，
1 < 4，所以list1（值为1的节点）成为合并链表的当前节点。然后，list1.next（值为3的节点）和list2.next（值为4的节点）再次进行比较。 -
合并完成：随着递归的进行，
list1和list2中剩余的节点将依次被合并。最终，当其中一个链表为空时，递归结束，另一个链表将直接连接到合并链表的末尾。 -
最终结果：经过上述步骤，我们得到合并后的有序链表：
合并后的链表: 1 -> 2 -> 3 -> 4 -> 5 -> 6
这个过程展示了 mergeTwoLists 函数如何通过递归地选择较小的节点并连接剩余的链表部分来合并两个有序链表。每次递归调用都简化了问题，直到问题变得足够简单（即其中一个链表为空），然后逐步返回并构建最终的合并链表。
