双向链表插入排序异常：仅单次交换后终止，请求排查修复

核心问题分析 #

你遇到的两个现象本质是同一个逻辑错误导致的：

• 加break只做一次交换就返回：说明你在交换后直接终止了排序循环，没有继续遍历后续节点
• 删break就无限循环：说明节点交换时的指针更新不完整，导致链表形成环，或者遍历指针无法正常推进

常见错误点及修正方向 #

1. 错误终止循环 #

如果你的代码在完成一次节点交换后就用break跳出了内层甚至外层循环，自然只会处理一个节点就停止。插入排序需要逐个处理从第二个节点开始的所有节点，内层循环是用来向前查找插入位置，不能在一次交换后就终止。

2. 节点交换/移动时指针更新不全 #

双向链表的节点移动需要处理4组指针（前后节点的prev/next），任何一组没处理好都会导致链表断裂或形成环：

• 移除当前节点时：要更新当前节点前驱的next，以及当前节点后继的prev
• 插入当前节点时：要更新插入位置前驱的next、当前节点的prev/next，以及插入位置后继的prev

修正后的参考实现 #

下面是正确的插入排序（移动节点而非交换节点，插入排序更适合移动而非交换相邻节点）代码：

#include "sort.h"

// 双向链表节点定义（假设）
typedef struct DListNode {
    int val;
    struct DListNode *prev;
    struct DListNode *next;
} DListNode;

void insertion_sort(DListNode **head) {
    if (!*head || !(*head)->next) return;

    DListNode *curr = (*head)->next;
    while (curr) {
        // 必须提前保存下一个节点，否则移动curr后会丢失后续节点的引用
        DListNode *next_node = curr->next;
        DListNode *prev_node = curr->prev;

        // 向前查找第一个小于等于curr的节点，确定插入位置
        while (prev_node && prev_node->val > curr->val) {
            prev_node = prev_node->prev;
        }

        // 如果curr已经在正确位置，直接处理下一个节点
        if (curr->prev == prev_node) {
            curr = next_node;
            continue;
        }

        // 步骤1：把curr从当前位置移除
        if (curr->prev) {
            curr->prev->next = curr->next;
        }
        if (curr->next) {
            curr->next->prev = curr->prev;
        }

        // 步骤2：把curr插入到prev_node的后面
        if (!prev_node) { // 插入到链表头部
            curr->next = *head;
            (*head)->prev = curr;
            *head = curr;
            curr->prev = NULL;
        } else { // 插入到链表中间或尾部
            curr->next = prev_node->next;
            if (prev_node->next) {
                prev_node->next->prev = curr;
            }
            prev_node->next = curr;
            curr->prev = prev_node;
        }

        // 处理下一个节点
        curr = next_node;
    }
}

关键注意事项 #

• 必须提前保存next_node：因为移动curr后，原来的curr->next指针会改变，无法再正确获取下一个要处理的节点
• 区分“交换节点”和“移动节点”：插入排序的核心是将当前节点插入前面的有序序列，移动节点比交换相邻节点更高效，也更容易避免指针错误
• 边界情况处理：要考虑插入到链表头部、尾部的情况，以及链表只有一个节点的特殊情况

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