10 - 合并两个有序链表

题目

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

示例：

输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4

解答

递归

作者：guanpengchn 链接：https://leetcode-cn.com/problems/two-sum/solution/hua-jie-suan-fa-21-he-bing-liang-ge-you-xu-lian-bi/

思路是，一个个拿出来比对，如果遇到小的，就往它的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的值给改变了

image-20190703214528102

发现是第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;
};

然后做不出来了。。

测试代码

测试代码主要解决两件事：

1. 根据数组，搭建链表。然后才能把链表传进函数mergeTwoLists里面 搭建链表的方法(Lists)，仿照two sum的测试代码中的BST函数

2. 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));
...

image-20190703202315846

List打印出来的next是null，然而打开它，还是能找到next的节点。

可能这是因为，console.log的时候，生成了一个快照。而点开的时候也调用了一下这个地址引用的内容，因此会出现结果的冲突。

pre也是类似，它的作用是存一下最新节点的变量。可以发现，它每次都指向了新的地址，里面有新的节点。

console.log()输出时是同步还是异步的问题

类似于如下的这个例子：

image-20190703205302721

解决方法，是console.log(JSON.stringify(a))强行转成字符串，就可以不怕更改了

当然这就需要多写一堆字，可以在vsc里面设置用户代码片段

{
    "Joey's log": {
    "prefix": "log",
    "body": ["console.log(\"=test=>\", \"${name}\", JSON.stringify(${name}));"],
    "description": "Log in test filter"
  }
}