LeetCode 21. Merge Two Sorted Lists：数组合并排序提交为何不通过？

这个问题听起来有点蠢，但我想知道为什么如下提交的数组合并实现不被接受：

var mergeTwoLists = function(list1, list2) {
  const mergerarr = list1.concat(list2);
  const mergesortfinal = mergerarr.sort((a, b) => a - b);
  return mergesortfinal;
};

核心原因 #

你大概率是在做合并两个有序链表的算法题，但你的代码完全搞错了处理对象：

• 题目输入的list1和list2不是普通数组，而是链表的头节点——每个节点是包含val（节点值）和next（下一个节点引用）的对象。用concat拼接的话，只是把两个头节点放到了数组里，根本没遍历链表取出所有节点值。
• 就算你先遍历链表提取所有val，最后返回的排序数组也不符合题目要求——题目需要你返回一个新的有序链表结构，不是普通数值数组。
• 退一步说，就算输入是数组，如果链表节点作为元素，sort((a,b)=>a-b)也会因为比较对象引用而失效，根本排不出正确顺序。

正确思路提示 #

要解决合并有序链表的问题，应该：

• 初始化一个虚拟头节点作为结果链表的起点
• 同时遍历两个输入链表的当前节点，每次选取值较小的节点，接到结果链表的尾部
• 当其中一个链表遍历完后，把另一个链表剩下的所有节点直接接到结果链表末尾
• 最后返回虚拟头节点的next，也就是结果链表的真正头节点

内容的提问来源于stack exchange，提问作者underwhelmedsyrup