问题

我正在尝试解决LeetCode问题148. 排序链表

给定一个链表的头节点 head，请返回升序排序后的链表。

我试图以递归的方式来解决它，然后再尝试更聪明的方法，因为我正在学习如何处理数据结构。

这是我的代码：

/**
 * 单链表的定义。
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val);
 *     this.next = (next===undefined ? null : next);
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function(head) {
    let previousNode = head
    if(!head){
        return head
    }
    let node = head.next
    if(!node){
        return head
    }
    let start = head
    let previousNode1 = head
    function sortList1(node, previousNode){
        if(node.next == null){
            return start
        }
        let temp = node.next;
        if(traverseFromHead(node)){
            start = node
        }
        previousNode1 = node
        return sortList1(temp, node)
    }
    return sortList1(node, previousNode)

    function traverseFromHead(node){
        let myPosition = start
        let inserted = false
        if(start.val > node.val){
            previousNode1.next = node.next
            node.next = start
            console.log("found in head excahange", node)
            return node;
        }
        let myprevious2 = start
        while(myPosition.next != null){
            if(myPosition.val >= node.val){
                console.log("before check start was", start, "with position at", myPosition.val, "for point", node.val, "my previous is", myprevious2.val)
                let temp = node.next
                myprevious2.next = node
                node.next = myPosition
                console.log("after update start is", start, "with position at", myPosition.val, "for point", node.val)
                return null
            }
            myprevious2 = myPosition;
            myPosition = myPosition.next
        }
        return false
    }
};

我无法使它正常工作；可能是我在逻辑或概念上做错了一些事情。

例如，对于链表 4→2→3→0，预期输出应该是 0→2→3→4，但我的代码产生的是 2→0。

我的代码中有什么问题？

/**
* Definition for singly-linked list.
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var sortList = function(head) {
let previousNode = head
if(!head){
return head
}
let node = head.next
if(!node){
return head
}
let start = head
let previousNode1 = head
function sortList1(node, previousNode){
if(node.next == null){
return start
}
let temp = node.next;
if(traverseFromHead(node)){
start = node
}
previousNode1 = node
return sortList1(temp, node)
}
return sortList1(node, previousNode)
function traverseFromHead(node){
let myPosition = start
let inserted = false
if(start.val > node.val){
previousNode1.next = node.next
node.next = start
console.log("found in head excahange", node)
return node;
}
let myprevious2 = start
while(myPosition.next != null){
if(myPosition.val>=node.val){
console.log("before check start was", start, "with position at", myPosition.val, "for point", node.val, "my previous is", myprevious2.val)
let temp = node.next
myprevious2.next = node
node.next = myPosition
// previousNode1.next = temp
console.log("after update start is", start, "with position at", myPosition.val, "for point", node.val)
return null
}
myprevious2 = myPosition;
myPosition = myPosition.next
}
return false
}
};

答案1

得分: 2

你尝试实现了插入排序。

以下是修复它工作不正确的问题：

• 递归函数的基本情况不正确。使用 if(node.next == null) 时，停止得太早了。可能需要将此尾节点移动到列表中的其他位置，但未将此节点的值与任何内容进行比较。停止条件应为 node == null。

• previousNode1 = node 未始终正确标识前一个节点。如果对 traverseFromHead 的调用将 node 移动到列表中的其他位置，则 previousNode1 不应更改，因为曾经是 node 之前的节点现在将成为您要处理的下一个节点之前的节点。同样的原因，您传递给递归调用的第二个参数大多数情况下是错误的：sortList1(temp, node)。

  有这么多变体的 previousNodeXX 变量有点令人不知所措。我建议至少消除 previousNode1 并继续使用 previousNode，将其也作为参数传递给 traverseFromHead。所以将其称为 traverseFromHead(node, previousNode)，确保您传递正确的第二个参数给 sortList1。需要区分两种情况：

  当 node 没有移动时，sortList1(temp, node) 是正确的，但是当 node 被移动时，应该是 sortList1(temp, previousNode)。您可以使用条件运算符区分：

  sortList1(temp, previousNode.next != node ? previousNode : node)
  

• traverseFromHead 仅在 if 情况下从当前位置移除节点，但在更一般的情况下忘记了执行相同的操作。在一般情况下，节点已插入，但未调整 previousNode.next，这意味着现在有两个节点的 next 属性指向 node。有几种正确的方法来解决这个问题。我建议在执行任何其他操作之前，在所有情况下执行节点提取操作。您可以将节点提取的代码放在 if 语句之前，以便它始终发生：

  previousNode.next = node.next // 应始终发生
  if(start.val > node.val){
  //...
  

• 我可以理解您为什么在循环内的 previousNode1.next = temp 中加入了注释。大多数情况下，确实需要这样做，但是当 node 没有移动时不需要！为了解决这个困境，在 node 已经在正确位置（相对于 previousNode）时执行快速退出。因此，在函数顶部执行以下操作：

  if (node.val >= previousNode.val) return null;
  

  现在您可以确保 node 将移动。

• traverseFromHead 具有奇怪的 while 条件。在上述更正的情况下，此 while 条件可以是 if 条件的相反，以便您可以在循环之后处理插入：

  while (myPosition.val < node.val)
  myprevious2 = myPosition;
  myPosition = myPosition.next
  }
  

以下是带有这些更正的代码：

var sortList = function(head) {
    let previousNode = head
    if(!head){
        return head
    }
    let node = head.next
    if(!node){
        return head
    }
    let start = head
    
    function sortList1(node, previousNode){
        if(node == null){ // 修正的基本情况
            return start
        }
        let temp = node.next;
        if(traverseFromHead(node, previousNode)){ // 传递第二个参数
            start = node
        }
        // 根据节点是否移动，前一个temp的节点不同
        return sortList1(temp, previousNode.next != node ? previousNode : node)
    }
    
    return sortList1(node, previousNode)

    function traverseFromHead(node, previousNode){ // 第二个参数
        if (node.val >= previousNode.val) return null; // 简单情况的快速退出
        previousNode.next = node.next // 始终首先提取节点
        if(start.val >= node.val){ // 相等也可以，所以>=
            node.next = start
            return node;
        }
        let myPosition = start.next // 可以从第二个节点开始迭代
        let myprevious2 = start
        while (myPosition.val < node.val) { // 查找插入位置
            myprevious2 = myPosition;
            myPosition = myPosition.next
        }
        // 现在执行重新插入
        myprevious2.next = node
        node.next = myPosition
        return null
    }    
};

其他备注

插入排序并不是最有效的排序算法，对于链表来说，实现性能更好的排序算法相对容易。

例如，参见链表上的归并排序

我在这里针对LeetCode挑战（剧透）调整了该解决方案：

var sortList = function(head) {
    if (!head || !head.next) return head; // 没有要排序的内容
    // 查找第一半的最后一个节点
    let tail = head;
    for (let fast = tail.next; fast?.next; fast = fast.next.next) {
        tail = tail.next;
    }
    // 将列表分成两半
    let head2 = tail.next;
    tail.next = null;
    // 递归排序两个较短的列表
    head = sortList(head);
    head2 = sortList(head2);
    // 合并两个排序的列表
    if (head.val > head2.val) [head2, head]

<details>
<summary>英文:</summary>

You have tried to implement insertion sort.

There are these issues that prevent it from working correctly:

* The base case of the recursive function is not correct. With `if(node.next == null)` you are stopping too early. It could well be that this tail node should be moved elsewhere in the list, yet this node&#39;s value is not compared with anything. The stop condition really should be `node == null`.

* `previousNode1 = node` is not always correctly identifying the previous node.  If the call to `traverseFromHead` *moved* `node` to elsewhere in the list, then `previousNode1` should not change, because what used to be the node before `node`, will now have become the node before the *next* node you want to process. For the same reason the second argument you pass in the recursive call is most often wrong: `sortList1(temp, node)`.

     It is a bit overwhelming to have that many variants of `previousNodeXX` variables. I would suggest to at least eliminate this `previousNode1` and continue to work with `previousNode`, passing it also as argument to `traverseFromHead`.  So call it as `traverseFromHead(node, previousNode)` and make sure you pass the correct second argument to `sortList1`. There are two cases to distinguish:

    When `node` wasn&#39;t moved, then `sortList1(temp, node)` is correct, but when `node` was moved, it should be `sortList1(temp, previousNode)`. You can make the distinction with a conditional operator:

    ```
    sortList1(temp, previousNode.next != node ? previousNode : node)
    ```

* `traverseFromHead` only removes the node from its current position in the `if` case, but forgets to do the same in the more general case. In the general case, the node *is* inserted, but `previousNode.next` is not adapted, meaning you now have two nodes whose `next` property point to `node`. There are several ways to do it right. I would suggest to perform the node-removal action in *all* cases before doing anyting else. You could place the code for node extraction *before* the `if` statement so that it always happens:

    ```
    previousNode.next = node.next // &lt;-- should always happen
    if(start.val &gt; node.val){
         //...
    ```

    
* I can understand why you put `previousNode1.next = temp` in comments inside the loop. Most often this needs to happen, *but not* when `node` didn&#39;t move! To solve this dilemma, perform a quick exit when `node` is already at its correct position (in comparison with `previousNode`). So at the top of the function do:

    ```
    if (node.val &gt;= previousNode.val) return null;
    ```

    Now you can be sure that `node` *will* move.

* `traverseFromHead` has a strange `while` condition. With the above corrections in place, this `while` condition can just be the opposite of the `if` condition, so that you can deal with the insertion *after* the loop: 

    ```
    while (myPosition.val &lt; node.val)
        myprevious2 = myPosition;
        myPosition = myPosition.next
    }
    ```

Here is your code with those corrections:

var sortList = function(head) {
let previousNode = head
if(!head){
return head
}
let node = head.next
if(!node){
return head
}
let start = head

function sortList1(node, previousNode){
if(node == null){ // Corrected base case
return start
}
let temp = node.next;
if(traverseFromHead(node, previousNode)){ // Pass the second argument
start = node
}
// Depending on whether node was moved, the node that precedes temp is different
return sortList1(temp, previousNode.next != node ? previousNode : node)
}
return sortList1(node, previousNode)
function traverseFromHead(node, previousNode){ // Second argument
if (node.val >= previousNode.val) return null; // Quick exit for trivial case
previousNode.next = node.next // Always first extract the node
if(start.val >= node.val){ // Equal is also good, so >=
node.next = start
return node;
}
let myPosition = start.next // Can start iteration at second node
let myprevious2 = start
while (myPosition.val < node.val) { // Look for the insertion spot
myprevious2 = myPosition;
myPosition = myPosition.next
}
// Now perform the re-insertion
myprevious2.next = node
node.next = myPosition
return null
}    

};

## Other remarks
Insertion sort is not the most efficient among sorting algorithms, and for linked lists it is quite easy to implement better performing sorting algorithms. 
See for instance [Merge sort on linked list](https://stackoverflow.com/questions/69649727/how-to-alphabetically-sort-a-linked-list-in-javascript/69651397#69651397)
I have here adapted that solution for the LeetCode challenge (spoiler):
>! <code>var sortList = function(head) {
>!     if (!head || !head.next) return head; // Nothing to sort
>!     // Find last node of first half
>!     let tail = head;
>!     for (let fast = tail.next; fast?.next; fast = fast.next.next) {
>!         tail = tail.next;
>!     }
>!     // Split list into two halves
>!     let head2 = tail.next;
>!     tail.next = null;
>!     // Recursively sort the two shorter lists
>!     head = sortList(head);
>!     head2 = sortList(head2);
>!     // Merge the two sorted lists
>!     if (head.val > head2.val) [head2, head] = [head, head2];
>!     tail = head;
>!     while (tail.next && head2) {
>!       if (tail.next.val > head2.val) [head2, tail.next] = [tail.next, head2];
>!       tail = tail.next;
>!     }
>!     tail.next ??= head2;
>!     return head;
>! };</code>
</details>
# 答案2
**得分**: 0
归并排序自然适用于链表。
在归并排序中，您可以认为合并两个大小为1的链表是微不足道的（只需将较高的头值放在较低的头值之后）。
扩展这个想法，如果您有两个已经排序的列表，那么将它们合并也很容易。只需创建一个新的列表，将两个列表中较高的值依次添加到新列表，直到两个列表都为空为止。
因此，您可以通过首先创建大小为1的两个列表（即您的列表的前两个元素）来执行归并排序。然后将它们合并。
然后创建一个大小为2的第二个列表（通过合并两个大小为1的列表）。
并继续执行，直到将整个原始列表合并为一个排序好的列表。
**递归**
要递归实现这个过程，首先编写一个合并函数，该函数给定两个已排序的列表，通过保留排序顺序将它们合并。
然后按照以下步骤实现排序：
1. 如果您的列表为空，则将列表作为结果返回。
2. 现在将第一个元素与排序（列表的其余部分）合并。
<details>
<summary>英文:</summary>
MergeSort naturally fits for linked lists.
In merge sort you consider that merging 2 size one lists is trivial (just put the higher head value after the lower one).
Extending that idea, if you have two already sorted lists, then it&#39;s easy to merge them as well. Just create a new list where you add the highest of both lists till both lists are empty.
So you can do a merge sort by creating first 2 lists of size 1. (ie. the first 2 elements of your list) Then merging them.
Then create a second list of size 2 (by merging 2 of size 1).
And continue until you have merged the entire original list into a sorted list.
**Recursion**
To implement this recursively first write a merge function that given two sorted lists merges them by preserving the sort order.
Then do the following to implement sort:
1. If your list is empty, then return the list as your result
2. Now merge the first element with sort(rest of the list)
</details>