双向链表插入排序异常求助：排序结果出现重复元素

核心排查方向 #

针对你遇到的元素重复问题，结合禁用sorted insertion的插入排序逻辑，重点检查insertionSort方法中的以下关键点：

1. 节点移除操作不彻底 #

插入排序需要先将当前待排序节点从原位置移除，再插入到正确位置。若移除时未正确更新前后节点的指针，会导致原节点残留，后续插入后出现重复：

• 必须同时处理前驱节点的next和后继节点的prev：

  // 错误示例：仅更新单边指针
  current.prev.next = current.next;
  // 正确处理：覆盖首尾节点的边界情况
  if (current.prev != null) {
      current.prev.next = current.next;
  }
  if (current.next != null) {
      current.next.prev = current.prev;
  }
  

• 移除后建议将当前节点的prev和next置为null，避免后续插入时干扰指针绑定

2. 插入节点时的指针重复绑定 #

插入新位置时，若未正确断开原节点的旧连接，或错误复用已移除节点的引用，会导致同一节点被多次插入：

• 插入时需同步更新四个指针：目标前驱的next、目标后继的prev、当前节点的prev和next：

  // 插入到targetNode之后的正确逻辑
  current.prev = targetNode;
  current.next = targetNode.next;
  if (targetNode.next != null) {
      targetNode.next.prev = current;
  }
  targetNode.next = current;
  

• 确保每次处理的是原链表中未被处理的节点，避免循环中重复操作同一节点实例

3. 循环边界条件错误 #

若循环未正确控制待处理节点范围，会导致某个节点被多次处理：

• 必须提前保存下一个待处理节点的引用，因为处理当前节点会改变原链表结构：

  Node current = head.next;
  while (current != null) {
      Node next = current.next; // 提前保存下一个节点
      // 执行节点的移除与插入逻辑
      current = next; // 移动到下一个待处理节点
  }
  

• 避免遗漏current = next的步骤，否则会陷入死循环或重复处理同一节点

4. 头尾节点的特殊场景处理 #

插入到链表头部或尾部时的指针处理错误，也可能引发重复：

• 插入头部时需更新链表的head指针，同时修正原头节点的prev：

  if (targetNode == null) { // 插入到链表头部
      current.next = head;
      head.prev = current;
      head = current;
      current.prev = null;
  }
  

针对你的输入用例的验证 #

输入链表为101 -> 10 -> 7 -> 1 -> 4，出现重复的1，大概率是处理4节点时，1节点的移除或插入逻辑出错：

• 检查处理4时，是否错误地重复插入了1节点，或4节点的移除操作未生效，导致原位置残留节点引发重复

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