如何实现链表原地排序 不创建新链表返回排序后的原链表

原代码问题梳理 #

• 类属性和实例属性混用：LinkedList是构造函数本身，不能直接通过它访问链表节点的value、next属性，实例方法内必须通过this指代当前操作的链表实例
• 边界判断逻辑错误：空链表判断应校验this.head是否为null，单节点判断应校验this.head.next是否为null，原代码直接取next.value会在单节点场景触发空指针报错
• 遍历逻辑失效：for循环未给索引i设置初始值，遍历过程中从未移动节点指针，始终停在head节点做比较，无法覆盖链表所有元素
• 缺失核心交换逻辑：代码仅给临时变量current重复赋值，从未修改节点的next指针调整节点位置，完全无法实现排序效果
• 返回值不符合要求：方法需要返回修改后的原链表，原代码返回拼写错误的字符串，和需求不匹配

符合要求的原地排序实现 #

要求不创建新链表、原地修改返回原链表，选择空间复杂度O(1)的冒泡排序实现最容易理解，全程仅调整原有节点的指针指向，不会生成新的链表节点：

LinkedList.prototype.orderList = function() {
  // 空链表、单节点链表本身有序，直接返回
  if (this.head === null || this.head.next === null) {
    return this;
  }

  let swapped;
  // 虚拟头节点，统一头节点和中间节点的交换逻辑
  const dummy = { next: this.head };
  // 标记已排序的链表尾部，减少无效遍历
  let lastSorted = null;

  do {
    swapped = false;
    let prev = dummy;
    let curr = dummy.next;

    while (curr.next !== lastSorted) {
      // 相邻节点值逆序，交换两个节点位置
      if (curr.value > curr.next.value) {
        const tempNext = curr.next;
        // 修改指针完成节点交换
        prev.next = tempNext;
        curr.next = tempNext.next;
        tempNext.next = curr;

        swapped = true;
        prev = tempNext;
      } else {
        // 顺序正常，指针向后移动
        prev = curr;
        curr = curr.next;
      }
    }
    // 本轮遍历到的最后一个节点已是当前最大值，更新已排序边界
    lastSorted = curr;
  } while (swapped); // 某轮无交换说明链表已有序，终止循环

  // 更新原链表头指针
  this.head = dummy.next;
  return this;
};

实现说明：

• 所有操作都在原链表节点上完成，没有新建任何链表节点，完全满足原地修改的要求
• 加入已排序边界标记，相比基础冒泡实现减少了大量重复遍历
• 虚拟头节点抹平了头节点交换的特殊逻辑，代码分支更少更稳定
• 最终返回修改后的原链表实例，符合调用预期

测试验证 #

// 对应给出的测试用例
const linkedList = new LinkedList();
linkedList.add(8);
linkedList.add(15);
linkedList.add(1);
const sortedList = linkedList.orderList();
// 遍历sortedList输出顺序为 1 -> 8 -> 15，结果正确

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