如何基于现有冒泡排序框架实现双向链表的排序？

你已经实现了单链表的冒泡排序，现在要适配双向链表，核心是在节点交换时同时维护prev和next两组指针的关联关系，下面是具体的修改点和完整代码：

需要调整的核心逻辑：节点交换时的指针维护 #

单链表冒泡排序只需要处理next指针，但双向链表必须同步更新prev指针，确保每个节点的前后指针都指向正确的节点。当需要交换current和它的下一个节点after时，需要完成以下6步指针调整：

• 保存after的下一个节点（避免丢失后续链表）
• 调整current和after的next指针，完成顺序互换
• 调整current和after的prev指针，互相指向对方
• 处理current原来的前驱节点prv：若prv不为空，同步更新它的next和after的prev；若为空，说明after成为新头节点，更新头指针
• 处理after原来的后继节点（即保存的临时节点）：若存在，更新它的prev指向current
• 更新遍历指针，继续后续比较

修改后的完整代码 #

#include <bits/stdc++.h>
using namespace std;

struct Node{
    int val;
    Node* prev;
    Node* next;
    Node(int x){
        val = x;
        prev = NULL;
        next = NULL;
    }
};

class DoubleLink{
public:
    Node* head;

    DoubleLink() { // 初始化头指针为NULL，避免野指针
        head = NULL;
    }

    void push(int x){
        Node* newnode = new Node(x);
        newnode->next = head;
        if(head != NULL){
            head->prev = newnode;
        }
        head = newnode;
    }

    void printList(Node* head){
        Node* current = head;
        cout<<endl;
        while(current != NULL){
            cout<<current->val<<" ";
            current = current->next;
        }
    }

    int getSize(Node* headref){
        int count =0;
        while(headref != NULL){
            count++;
            headref = headref->next;
        }
        return count;
    }

    void bubbleSort(Node*& headref){ // 参数用指针引用，确保头节点变化同步到类成员
        Node* lswap = NULL;
        int sz = getSize(headref);
        while(sz--){
            Node* current = headref;
            Node* prv = NULL;
            Node* cswap = NULL;
            while(current->next != lswap){
                Node* after = current->next;
                if(current->val > after->val){
                    Node* temp = after->next; // 保存after的后继节点

                    // 调整next指针
                    current->next = temp;
                    after->next = current;

                    // 调整prev指针
                    after->prev = current->prev;
                    current->prev = after;

                    // 处理current的前驱节点
                    if(prv != NULL){
                        prv->next = after;
                        after->prev = prv;
                    } else {
                        // 交换后after成为新头节点
                        headref = after;
                    }

                    // 处理temp节点（若存在）
                    if(temp != NULL){
                        temp->prev = current;
                    }

                    prv = after;
                    cswap = current;
                } else {
                    prv = current;
                    current = current->next;
                }
            }
            if(cswap == NULL)
                break; // 无交换操作，说明链表已有序，提前退出
            else
                lswap = cswap;
        }
    }
};

int main(){
    DoubleLink list;
    int size;
    cout<<"请输入数字个数："<<endl;
    cin>>size;
    int numbers[size];
    cout<<"请输入数字："<<endl;
    for(int i=0;i<size;i++){
        cin>>numbers[i];
    }
    for(int i=0;i<size;i++){
        list.push(numbers[i]);
    }
    cout<<"排序前："<<endl;
    list.printList(list.head);
    cout<<"\n排序后："<<endl;
    list.bubbleSort(list.head);
    list.printList(list.head);
    cout<<endl;
}

额外补充的细节 #

• 给DoubleLink类添加了构造函数，确保head初始化为NULL，避免野指针问题
• 将bubbleSort的参数改为指针引用Node*& headref，这样交换导致头节点变化时，类成员head会同步更新
• 所有指针调整都保证了双向链表的前后关联不断裂，每一步都对应维护prev和next的指向

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