Java双向链表实现快速排序（取中间节点为pivot）的代码问题排查

现有代码核心错误 #

• pivot选取逻辑完全错误：你当前代码中Node pivot = (Node) peek(5);选取的节点和当前排序的[left, right]区间无关，根本不是当前区间的中间节点，分区逻辑完全失效。
• 指针移动操作未赋值：两处p.getNext();仅调用了获取下一个节点的方法，没有将返回值赋值给p，p指针根本不会移动，分区逻辑卡死。
• 空指针风险：当p为null时，代码后续仍直接调用p.getItem()，会直接触发空指针异常导致程序崩溃。
• pivot不属于当前排序区间：你选取的pivot不在[left, right]区间内，最后交换p和pivot值的操作完全没有意义，无法完成分区。

修复后代码实现 #

1. 辅助方法：获取区间中间节点 #

// 获取[left, right)区间的中间节点
private Node getMid(Node left, Node right) {
    Node slow = left;
    Node fast = left;
    while (fast != right && fast.getNext() != right) {
        slow = slow.getNext();
        fast = fast.getNext().getNext();
    }
    return slow;
}

2. 修复后的partition方法 #

public Node partition(Node left, Node right) {
    // 选取当前区间的中间节点作为pivot，先把pivot的值交换到区间末尾，避免分区过程中pivot移动
    Node pivot = getMid(left, right);
    int pivotVal = (int) pivot.getItem();
    // 找到区间最后一个节点（right的前一个节点）
    Node lastNode = left;
    while (lastNode.getNext() != right) {
        lastNode = lastNode.getNext();
    }
    // 交换pivot和末尾节点的值，统一用末尾值做比较基准
    int temp = (int) lastNode.getItem();
    lastNode.setItem(pivot.getItem());
    pivot.setItem(temp);

    Node p = left.getPrev();
    for (Node q = left; q != right; q = q.getNext()) {
        if ((int) q.getItem() <= pivotVal) {
            p = (p == null) ? left : p.getNext();
            // 交换p和q的值
            temp = (int) p.getItem();
            p.setItem(q.getItem());
            q.setItem(temp);
        }
    }
    // 把基准值交换到最终位置，确定pivot的排序后坐标
    Node pivotFinalPos = (p == null) ? left : p.getNext();
    temp = (int) pivotFinalPos.getItem();
    pivotFinalPos.setItem(lastNode.getItem());
    lastNode.setItem(temp);
    return pivotFinalPos;
}

3. 修复后的快速排序主逻辑 #

public void QuickSort(Node left, Node right) {
    // 递归终止条件：区间无效/只有一个元素
    if (right != null && left != right && left != right.getNext()) {
        Node p = partition(left, right);
        QuickSort(left, p);
        QuickSort(p.getNext(), right);
    }
}

调用方式说明 #

如果需要对整个双向链表排序，假设链表头节点为head，尾节点的next为null，初始调用方式为：

QuickSort(head, null);

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