双向链表不交换数据交换节点位置的C++代码问题求助

我尝试在不交换节点数据的前提下，交换双向链表中两个指定位置的节点，但代码运行结果不符合预期，具体情况如下：

• 链表长度：20
• 链表元素：2158 2398 300 2268 3655 765 3792 4038 1761 4762 1292 3200 3882 962 488 1938 3757 3122 302 640
• 待交换位置：9 和 12
• 正确结果：2158 2398 300 2268 3655 765 3792 4038 3200 1292 4762 1761 3882 962 488 1938 3757 3122 302 640
• 代码运行结果：2158 2398 300 2268 3655 765 3792 4038 3200 4762 1292 1761 3882 962 488 1938 3757 3122 302 640

我的代码如下：

/*struct ListNode {
        int val;
        ListNode *left;
        ListNode *right;
        ListNode(int x = 0, ListNode *l = nullptr, ListNode* r = nullptr) : val(x), left(l), right(r) {}
    };
    */
    
    ListNode* reverse(ListNode* head, int a, int b) {
        //To Do
        if(a==b) return head;
        ListNode* h = head;
        ListNode* anode = new ListNode;
        ListNode* bnode = new ListNode;
        int n(1);
        for(int i(1); h!= nullptr; i++){
            if(i == a){
                anode = h;
                
            }
            if(i == b){
                bnode = h;
                // break; // now h = bnode
            }
            ++n;
            h= h->right;
        }
        ListNode* bleft = new ListNode;
        ListNode* bright = new ListNode;
        bright = bnode->right;
        bleft = bnode->left;
        
        bnode->right = anode->right;
        bnode->right->left = bnode;
        if(a==1){
            
        }
        else{
            bnode->left = anode->left;
            bnode->left->right = bnode;
        }
        
        anode->left = bleft;
        bleft->right = anode;
        if(bright ==nullptr){
            anode->right = nullptr;
            
        }
        else{
            anode->right = bright;
            bright->left = anode;
        }
        if(a==1) return bnode;
        return head;
    }

问题分析与修正方案 #

你的代码核心错误在于未完整保存节点的前驱后继就修改指针，导致中间节点的指针指向混乱，尤其在两个待交换节点不相邻时问题更明显。此外，代码中不必要地使用new ListNode初始化指针，会导致内存泄漏和错误的节点指向。

以下是修正后的代码：

/*struct ListNode {
        int val;
        ListNode *left;
        ListNode *right;
        ListNode(int x = 0, ListNode *l = nullptr, ListNode* r = nullptr) : val(x), left(l), right(r) {}
    };
    */
    
ListNode* swapNodes(ListNode* head, int a, int b) {
    if (a == b) return head;
    // 确保a小于b，简化逻辑处理
    if (a > b) {
        int temp = a;
        a = b;
        b = temp;
    }

    ListNode *anode = nullptr, *bnode = nullptr;
    ListNode *current = head;
    int pos = 1;
    // 找到待交换的两个节点
    while (current != nullptr) {
        if (pos == a) anode = current;
        if (pos == b) bnode = current;
        current = current->right;
        pos++;
    }

    // 保存两个节点的前驱和后继指针
    ListNode *anodeLeft = anode->left;
    ListNode *anodeRight = anode->right;
    ListNode *bnodeLeft = bnode->left;
    ListNode *bnodeRight = bnode->right;

    // 将anode插入到bnode原来的位置
    if (bnodeLeft != nullptr) {
        bnodeLeft->right = anode;
    }
    anode->left = bnodeLeft;
    anode->right = bnodeRight;
    if (bnodeRight != nullptr) {
        bnodeRight->left = anode;
    }

    // 将bnode插入到anode原来的位置
    if (anodeLeft != nullptr) {
        anodeLeft->right = bnode;
    } else {
        // 如果anode是原头节点，更新头指针为bnode
        head = bnode;
    }
    bnode->left = anodeLeft;
    bnode->right = anodeRight;
    if (anodeRight != nullptr) {
        anodeRight->left = bnode;
    }

    return head;
}

关键修正点 #

1. 统一位置顺序：增加a和b的大小交换，确保a < b，避免重复处理逻辑。
2. 移除不必要的节点创建：直接用指针指向链表中已存在的节点，避免内存泄漏。
3. 完整保存指针：先保存两个节点的所有前驱后继，再进行指针修改，防止修改过程中指针指向被覆盖。
4. 正确处理头节点：当待交换节点是原头节点时，及时更新链表的头指针。
5. 分离插入逻辑：分别处理两个节点的插入操作，确保每个节点的前驱和后继都正确指向。

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