基于指针的链表冒泡排序交换功能失效问题求助

你实现的基于指针的链表冒泡排序存在严重的指针逻辑错误，导致链表结构被破坏，最终打印时无输出。以下是问题分析和修复方案：

原代码中的核心错误 #

void bubbleSort()
{
    if (!head || !head->next) // checks if list is empty or singleton
    {
        std::cout << "already sorted\n";
        return;
    }

    bool swapped; // checks if a pass occured with no swaps

    Node* current;
    Node* lastSorted = NULL;

    do {
        swapped = false;
        current = head;

        while (current->next != lastSorted)
        {
            if (current->data > current->next->data)
            {
                Node* temp = current->next;
                temp->next = current;
                temp->next->next = current->next->next; // 逻辑完全混乱的一行

                current = temp;
            }
            current = current->next;
        }
    } while (swapped);
}

1. 指针赋值逻辑混乱：当执行temp->next = current后，current->next已经指向temp，此时current->next->next就是temp->next（也就是current），这会导致current->next指向自己，形成循环链表。
2. 未处理前节点和头节点：交换节点时，没有修改当前节点的前一个节点的next指针，也没有在交换头两个节点时更新head，导致链表断裂。
3. 未标记交换状态：交换节点后没有设置swapped = true，导致循环只会执行一次，且无法继续排序。

修复后的冒泡排序实现 #

void bubbleSort()
{
    if (!head || !head->next)
    {
        std::cout << "already sorted\n";
        return;
    }

    bool swapped;
    Node* lastSorted = nullptr;
    Node* prev = nullptr; // 跟踪当前节点的前一个节点

    do {
        swapped = false;
        prev = nullptr;
        Node* current = head;

        while (current->next != lastSorted)
        {
            if (current->data > current->next->data)
            {
                Node* temp = current->next;
                // 交换current和temp的位置
                current->next = temp->next;
                temp->next = current;

                // 更新前节点的指针或head
                if (prev == nullptr)
                {
                    head = temp; // 交换的是头节点，更新head
                }
                else
                {
                    prev->next = temp; // 更新前节点的next
                }

                swapped = true;
                // 交换后，current的位置不变，prev变为temp
                prev = temp;
            }
            else
            {
                // 未交换，移动prev和current
                prev = current;
                current = current->next;
            }
        }
        lastSorted = current; // 最后一个节点已排序，下次循环不用再处理
    } while (swapped);
}

修复关键点说明 #

• 跟踪前节点prev：用于在交换中间节点时，修改前一个节点的next指针，避免链表断裂。
• 分情况处理头节点：当prev为空时，说明交换的是头两个节点，需要更新head指针。
• 正确的指针交换顺序：先保存temp的next，再依次修改current->next、temp->next，最后更新prev或head。
• 标记交换状态：每次交换后设置swapped = true，确保循环能继续执行直到完全排序。
• 更新lastSorted：每次循环结束后，将最后一个已排序的节点记录下来，减少后续循环的次数，提升效率。

测试这个修复后的函数，无论是未排序还是已排序的链表，都能正常打印输出，且排序功能正常。

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