Java递归快速排序重复调用致列表元素翻倍问题求助

问题根源很明确：你用了静态的sortedList。静态成员属于类级别的共享变量，第一次排序后它会保留所有元素，第二次调用quicksortPrice时，不会自动清空旧数据，直接往里面追加新的排序结果，自然就出现元素翻倍的情况。而如果在调用前手动清空这个静态列表，递归过程中所有子调用都会共享这个被清空的列表，导致排序逻辑完全混乱。

解决方案：移除静态变量，让排序方法每次生成独立的结果链表 #

核心思路是让每次排序请求都创建独立的结果容器，递归过程中通过返回子链表并合并的方式完成排序，不再依赖共享的静态列表。

修改后的代码示例：

// 移除原来的静态sortedList变量
public static dlinkedList quicksortPrice(dlinkedList list) {
    // 空链表直接返回空结果
    if (list.head == null) {
        return new dlinkedList();
    }

    dlinkedList smaller = new dlinkedList();
    dlinkedList greater = new dlinkedList();
    Node pivotNode = list.tail;
    Item pivot = pivotNode.data;

    // 遍历链表，将元素分到小于、大于基准的子链表中
    Node current = list.head;
    while (current != null && current != pivotNode) {
        if (current.data.price < pivot.price) {
            smaller.addAtEndOfList(current.data);
        } else if (current.data.price > pivot.price) {
            greater.addAtEndOfList(current.data);
        } else {
            // 等于基准的元素暂时归入smaller，后续合并时统一处理
            smaller.addAtEndOfList(current.data);
        }
        current = current.next;
    }

    // 递归排序子链表
    dlinkedList sortedSmaller = quicksortPrice(smaller);
    dlinkedList sortedGreater = quicksortPrice(greater);

    // 创建结果链表，合并排序后的左子链表、基准、右子链表
    dlinkedList result = new dlinkedList();
    // 追加左子链表
    appendList(result, sortedSmaller);
    // 追加基准元素
    result.addAtEndOfList(pivot);
    // 追加右子链表
    appendList(result, sortedGreater);

    return result;
}

// 辅助方法：将source链表的所有元素追加到target链表末尾
private static void appendList(dlinkedList target, dlinkedList source) {
    Node current = source.head;
    while (current != null) {
        target.addAtEndOfList(current.data);
        current = current.next;
    }
}

关键修改点说明： #

1. 移除静态变量：每次调用quicksortPrice都会创建全新的链表容器，彻底避免了多调用之间的状态共享。
2. 递归合并子链表：递归排序左右子链表后，将左子链表、基准元素、右子链表依次合并成最终结果，符合快速排序的分治逻辑。
3. 修复遍历逻辑：原来的y.next != null会漏掉链表中的最后一个非基准元素，现在改为遍历到基准节点前，确保所有元素都被处理。

这样修改后，无论你调用多少次quicksortPrice，每次都会返回一个独立的、正确排序后的新链表，不会出现元素累加的问题。

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