题目
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
解答
递归
作者：guanpengchn 链接：
思路是，一个个拿出来比对，如果遇到小的，就往它的next后面贴链表。不断重复这个过程，直至遇到了null
这样做会直接破坏原有的l1或l2，不过题目中是允许的。
var mergeTwoLists = function(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;
}
};
Runtime: 68 ms, faster than 66.67% of JavaScript online submissions forMerge Two Sorted Lists.
Memory Usage: 35.2 MB, less than 90.02% of JavaScript online submissions for Merge Two Sorted Lists.
指针
指针的思路是，做一个-1节点，再有一个指针，指向最新的那个节点。
然后跑循环，每次比对小的那个贴到指针节点的后面。最后输出开头-1节点的后面那个节点。
var mergeTwoLists = function(l1, l2) {
const result = new ListNode(-1);
let index = result;
while (l1 !== null && l2 !== null) {
if (l1.val <= l2.val) {
index.next = l1;
l1 = l1.next;
} else {
index.next = l2;
l2 = l2.next;
}
index = index.next;
}
index.next = l1 === null ? l2 : l1;
return result.next;
};
Runtime: 72 ms, faster than 31.06% of JavaScript online submissions for Merge Two Sorted Lists.
Memory Usage: 34.9 MB, less than 99.94% of JavaScript online submissions for Merge Two Sorted Lists.
感觉这种思路，和我的思路很像，但要好很多。这里用了一个-1节点，一下子回避了很多问题。
比如说，开始的节点留哪个？是不是要l1和l2做个判断，留一开始最小的那个。那样思路的话就一下子变得很复杂了。
还有把指针直接贴上去的做法也是，我是想着根据val自己生成一个节点，然后把节点贴上去。其实可以直接贴上去的。。
探险过程
思路是这样的，拿来的两个链表，一个个摸出val，然后比大小。小的放前面，大的放后面，然后塞到之前的链表后面
const linkTwo = function(l1, l2) {
// console.log("=test=>", "l1 1", JSON.stringify(l1));
let result = l1.val <= l2.val ? l1 : l2;
// console.log("=test=>", "l1 2", JSON.stringify(l1));
result.next = l1.val <= l2.val ? l2 : l1;
// console.log("=test=>", "l1 3", JSON.stringify(l1));
return result;
};
然后就发现了问题，赋值之后把l1的值给改变了
发现是第5行的缘故。
第3行当中，是吧result这个变量，指向l1这个地址。因此5行result.next调用的是l1.next这个内容。因此是在把l2的值，覆盖掉l1.next了。
因此直接塞入链表不可行，得拿出每个节点的val，然后自己生成一个链表才行
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var mergeTwoLists = function(l1, l2) {
if (!l1.val || !l2.val) {
return;
}
let result = l1.val <= l2.val ? new ListNode(l1.val) : new ListNode(l2.val);
result.next = l1.val <= l2.val ? new ListNode(l1.val) : new ListNode(l2.val);
let index = result.next;
let l1Index = l1.next;
let l2Index = l2.next;
while (l1Index && l2Index) {
if (l1Index.val <= l2Index.val) {
index.next = new ListNode(l1Index.val);
index.next.next = new ListNode(l2Index.val);
} else {
index.next = new ListNode(l2Index.val);
index.next.next = new ListNode(l1Index.val);
}
index = index.next.next;
l1Index = l1Index.next;
l2Index = l2Index.next;
}
if (l1Index) {
index.next = l1Index;
} else {
index.next = l2Index;
}
return result;
};
然后做不出来了。。
测试代码
测试代码主要解决两件事：
mergeTwoLists得出的结果是链表，需要判断两个链表是否一致 判断结果的方法(ensure)，就是从头到尾一个个val进行判断
/**
*
* @param {ListNode} ans：输入的answer
* @param {ListNode} target：答案
* @param {number} index：报错标记符
*/
const ensure = (ans, target, index) => {
let ansTemp = ans;
let targetTemp = target;
while (ansTemp !== null && targetTemp !== null) {
if (ansTemp.val !== targetTemp.val) {
wrongMsg(ans, target, index);
break;
} else {
ansTemp = ansTemp.next;
targetTemp = targetTemp.next;
}
}
};
/**
*
* @param {Array} arr
* @returns {ListNode}
*/
var Lists = function(arr) {
function ListNode(val) {
this.val = val;
this.next = null;
}
let List = null;
const insertNode = function(List, newNode) {
if (List.next === null) {
List.next = newNode;
} else {
insertNode(List.next, newNode);
}
};
const insert = function(val) {
const newNode = new ListNode(val);
if (List === null) {
List = newNode;
} else {
insertNode(List, newNode);
}
};
arr.forEach(itemVal => insert(itemVal));
return List;
};
const TEST_DATA = [
{
inputs: [[1, 2, 4], [1, 3, 4]],
target: Lists([1, 1, 2, 3, 4, 4])
}
];
// ========== test ===========
const test = () => {
for (let index = 0; index < TEST_DATA.length; index++) {
const test = TEST_DATA[index];
const l1 = Lists(test.inputs[0]);
const l2 = Lists(test.inputs[1]);
const ans = mergeTwoLists(l1, l2);
ensure(ans, test.target, index);
}
};
优化一下List
感觉之前的逻辑太复杂了，存一下之前的节点就行了。毕竟都是引用的，肯定能找到。
/**
*
* @param {Array} arr
* @returns {ListNode}
*/
var Lists = function(arr) {
function ListNode(val) {
this.val = val;
this.next = null;
}
let List = null;
let pre = null;
const insert = function(val) {
const node = new ListNode(val);
if (List === null) {
List = node;
} else {
pre.next = node;
}
pre = node;
};
arr.forEach(itemVal => insert(itemVal));
return List;
};
感觉一下子少了很多代码
一个有趣的发现
如果在这里面打印会发现：
...
const insert = function(val) {
if (List === null) {
List = new ListNode(val);
pre = List;
} else {
pre.next = new ListNode(val);
pre = pre.next;
}
console.log("=test=>", "List", List); // 打印
console.log("=test=>", "pre", pre); // 打印
};
arr.forEach(itemVal => insert(itemVal));
...
List打印出来的next是null，然而打开它，还是能找到next的节点。
可能这是因为，console.log的时候，生成了一个快照。而点开的时候也调用了一下这个地址引用的内容，因此会出现结果的冲突。
pre也是类似，它的作用是存一下最新节点的变量。可以发现，它每次都指向了新的地址，里面有新的节点。
类似于如下的这个例子：
解决方法，是console.log(JSON.stringify(a))强行转成字符串，就可以不怕更改了
当然这就需要多写一堆字，可以在vsc里面设置用户代码片段
{
"Joey's log": {
"prefix": "log",
"body": ["console.log(\"=test=>\", \"${name}\", JSON.stringify(${name}));"],
"description": "Log in test filter"
}
}
