双向链表(Doubly Linked List)冒泡排序后头指针位置异常求助

问题根因 #

• swap函数指针更新不全：交换两个相邻节点时仅修改了节点自身的前后指针，未同步更新pointer1前驱节点的后继指针、pointer2后继节点的前驱指针，导致链表链路断裂，节点关联关系混乱，最终头指针定位错误。
• 循环边界冗余：外层循环条件i <= size会多执行一次无意义的遍历，虽不是核心问题但会降低排序效率。

修复方案 #

1. 修复swap函数 #

补充缺失的相邻节点指针更新逻辑，同时增加头节点自动更新处理：

struct DoubleNode *DoubleDynamic::swap( DoubleNode *pointer1,  DoubleNode *pointer2) {
    DoubleNode* temp = pointer2->next;
    // 同步更新pointer1前驱节点的后继指针
    if (pointer1->prev != NULL) {
        pointer1->prev->next = pointer2;
    }
    // 同步更新pointer2后继节点的前驱指针
    if (temp != NULL) {
        temp->prev = pointer1;
    }
    pointer2->next = pointer1;
    pointer2->prev = pointer1->prev;
    pointer1->next = temp;
    pointer1->prev = pointer2;
    // 若交换后pointer2成为新头节点，直接更新head
    if (pointer2->prev == NULL) {
        head = pointer2;
    }
    return pointer2;
}

2. 优化sort函数循环边界 #

将外层循环的判断条件从i <= size修改为i < size，减少冗余遍历：

for (int i = 0; i < size; ++i)

额外注意 #

调用sort函数时请确保传入的size参数和链表实际节点数完全一致，避免出现越界访问或未完成排序的问题。

内容的提问来源于stack exchange，提问作者Tarık