LeetCode 148. Sort List递归实现错误排查：输出不符预期

你的代码尝试用递归实现链表的插入排序，但存在几个关键错误导致输出异常：

核心问题点 #

• 递归终止条件错误：sortList1的终止条件是node.next == null，这会跳过对最后一个节点的处理。比如输入中的0节点，当递归到它时直接返回start，根本没执行插入逻辑。
• 原节点前驱的next未正确更新：在traverseFromHead中插入节点后，注释掉了previousNode1.next = temp，这会导致原链表中留下被移动节点的旧引用，造成节点丢失或链表结构混乱。
• 尾部插入逻辑缺失：当待插入节点的值比已排序链表所有节点都大时，没有将其接到链表末尾，导致该节点被丢弃。
• 返回值处理逻辑混乱：traverseFromHead返回多种类型的值（node、null、false），sortList1中的判断逻辑无法正确处理所有情况，导致start更新错误。

修正后的递归插入排序实现 #

下面是修复后的代码，同时简化了逻辑，确保每个节点都被正确插入到已排序链表中：

/**
 * 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) {
    // 空链表或单个节点直接返回
    if (!head || !head.next) return head;

    // 递归排序剩余链表，得到已排序的子链表
    let sorted = sortList(head.next);
    let curr = sorted;
    let prev = null;

    // 找到当前节点要插入的位置
    while (curr && curr.val < head.val) {
        prev = curr;
        curr = curr.next;
    }

    // 插入到头部
    if (!prev) {
        head.next = sorted;
        return head;
    }
    // 插入到中间或尾部
    prev.next = head;
    head.next = curr;
    return sorted;
};

修正说明 #

1. 正确的递归逻辑：先递归排序当前节点之后的所有节点，得到已排序的子链表，再将当前节点插入到该子链表的正确位置，符合插入排序的递归思路。
2. 完整的插入处理：涵盖了插入到头部、中间、尾部的所有情况，确保每个节点都被正确放置。
3. 清晰的逻辑流程：避免了全局变量的混乱引用，每个递归调用只处理当前节点的插入，逻辑更易维护。

测试输入4→2→3→0时，该代码会正确返回0→2→3→4。

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