98 lines
3.0 KiB
JavaScript
98 lines
3.0 KiB
JavaScript
/**
|
||
* 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}
|
||
*/
|
||
const mergeTwoLists = function (list1, list2) {
|
||
|
||
};
|
||
|
||
function ListNode(val, next) {
|
||
this.val = (val === undefined ? 0 : val);
|
||
this.next = (next === undefined ? null : next);
|
||
}
|
||
|
||
/*
|
||
遍历两个链表，如果l1的值小于l2的值，就创建一个新的节点，把l1的值放入这个新节点中，之后把这个新节点
|
||
拼接到l3中，之后返回代表l3的头节点即可
|
||
*/
|
||
function f1(list1, list2) {
|
||
const dummyHead = new ListNode(0); // 哑节点，用于拼接链表
|
||
let current = dummyHead;
|
||
|
||
while (list1 !== null || list2 !== null) {
|
||
if (list1 && list2) {
|
||
if (list1.val <= list2.val) {
|
||
current.next = new ListNode(list1.val);
|
||
list1 = list1.next;
|
||
} else {
|
||
current.next = new ListNode(list2.val);
|
||
list2 = list2.next;
|
||
}
|
||
current = current.next;
|
||
} else if (list1 === null) { // 当list1为空时直接将list2剩余部分拼接即可
|
||
current.next = list2;
|
||
break;
|
||
} else if (list2 === null) { // 当list2为空时直接将list1剩余部分拼接即可
|
||
current.next = list1;
|
||
break;
|
||
}
|
||
}
|
||
return dummyHead.next;
|
||
}
|
||
|
||
/*
|
||
思路和上面的一致，上面的效率之所以慢是因为花费了大量的时间在创建新节点上，这个操作虽然直观，但是
|
||
显得多余。
|
||
*/
|
||
function f2(list1, list2) {
|
||
const dummyHead = new ListNode(0); // 哑节点，用于拼接链表
|
||
let current = dummyHead;
|
||
|
||
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;
|
||
}
|
||
|
||
// 如果 list1 或者 list2 还有剩余节点，直接拼接到结果链表
|
||
if (list1 !== null) {
|
||
current.next = list1;
|
||
} else if (list2 !== null) {
|
||
current.next = list2;
|
||
}
|
||
return dummyHead.next;
|
||
}
|
||
|
||
/*
|
||
利用递归，思考递归过程，首先思考f3的作用，f3的作用非常单一，就是合并两个有序链表，合并完成之后，使其
|
||
仍然有序，假设list1[0]比list2[0]小，那么list1[0]一定是合并后链表的头节点，我们只需把list1[1:]和list2
|
||
继续做交给f3，把合并后的头节点作为list1[0]的next,不就完成整个递归过程了嘛！
|
||
*/
|
||
function f3(l1, l2) {
|
||
if (l1 === null) {
|
||
return l2; // 如果 l1 空了，返回 l2
|
||
} if (l2 === null) {
|
||
return l1; // 如果 l2 空了，返回 l1
|
||
} if (l1.val < l2.val) {
|
||
// 如果 l1 的值小于 l2，则 l1 当前节点连接到后面的结果
|
||
l1.next = mergeTwoLists(l1.next, l2);
|
||
return l1; // 返回 l1，表示 l1 的节点被连接到了合并后的链表中
|
||
}
|
||
// 否则，l2 当前节点连接到后面的结果
|
||
l2.next = mergeTwoLists(l1, l2.next);
|
||
return l2; // 返回 l2，表示 l2 的节点被连接到了合并后的链表中
|
||
}
|