基于链表的C++ Deque反转方法异常及后续功能故障排查

问题根源分析 #

你遇到的问题核心是：普通单链表反转只处理next指针，但双端队列（Deque）依赖head/tail双指针和双向链表的prev/next双向关联，只反转next链会导致：

• getRear()仍指向反转前的尾节点（现在是新的头节点），返回旧值
• deleteLast()操作时，会访问新尾节点（原头节点）的prev指针（未正确更新，可能为野指针），导致崩溃

正确的reverse实现步骤 #

基于双向链表的Deque反转需要完成3件事：

• 遍历所有节点，交换每个节点的prev和next指针
• 交换Deque的head和tail指针
• 修正新头/新尾的边界指针（新头的prev设为null，新尾的next设为null）

代码示例与修正 #

假设你的Deque节点定义和原错误reverse方法如下：

struct Node {
    int val;
    Node* prev;
    Node* next;
    Node(int x) : val(x), prev(nullptr), next(nullptr) {}
};

class Deque {
private:
    Node* head;
    Node* tail;
public:
    // 其他方法...
    void reverse() {
        // 错误实现：只反转next链，没处理prev和head/tail交换
        Node* curr = head;
        Node* temp = nullptr;
        while (curr != nullptr) {
            temp = curr->next;
            curr->next = curr->prev;
            // 遗漏：交换prev指针
            curr = temp;
        }
        // 遗漏：交换head和tail
    }
    int getRear() { return tail->val; }
    void deleteLast() {
        if (tail == nullptr) return;
        Node* temp = tail;
        tail = tail->prev;
        if (tail != nullptr) tail->next = nullptr;
        else head = nullptr; // 队列空了
        delete temp;
    }
};

修正后的reverse方法 #

void reverse() {
    // 空队列或单节点直接返回
    if (head == nullptr || head == tail) return;

    Node* curr = head;
    Node* temp = nullptr;
    while (curr != nullptr) {
        // 交换当前节点的prev和next
        temp = curr->prev;
        curr->prev = curr->next;
        curr->next = temp;
        // 移动到下一个节点（原来的prev，因为已经交换）
        curr = curr->prev;
    }

    // 交换head和tail指针
    temp = head;
    head = tail;
    tail = temp;
}

验证逻辑 #

• 反转后，head指向原尾节点，tail指向原头节点，getRear()会返回原头节点的值（符合预期）
• deleteLast()会操作新的tail（原头节点），其prev已经被正确设置为原头节点的next（反转后变成prev），不会出现野指针访问

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