双向循环链表使用指针交换节点时头节点交换失败问题排查

核心错误点 #

• 仅处理了「node1是头且node2是尾」这一种头节点相关场景，其余涉及头节点和非尾节点交换的场景完全没有适配，也没有统一的头指针更新逻辑，这是出现交换头节点时实际操作的是head->next的根本原因。
• 相邻节点交换分支的指针赋值逻辑错误，完全搞反了相邻节点的前后指向关系。
• 单独处理头尾交换的分支逻辑冗余且错误，完全可以和通用交换逻辑合并，不需要单独写分支。

修正思路 #

1. 删掉冗余的头尾节点单独判断分支，所有场景通用一套指针交换逻辑
2. 修正相邻节点的指针赋值规则
3. 交换完节点指针后统一判断头节点归属：如果原node1是头节点，交换后头节点改为node2；如果原node2是头节点，交换后头节点改为node1
4. 原updateNode逻辑无需修改可以正常复用

修正后完整代码 #

template<class T>
void LinkedList<T>::updateNode(Node<T> *node) {
    node->prev->next = node;
    node->next->prev = node;
}

template<class T>
void LinkedList<T>::swap(Node<T> *node1, Node<T> *node2) {
    if (!contains(node1) || !contains(node2)) 
        return;

    if (node1 == node2)
        return;
    
    // 统一处理node2在node1前面的相邻场景，保证后续判断时node1始终在node2前面
    if (node2->next == node1 && node1->prev == node2) {
        Node<T> *temp = node1;
        node1 = node2;
        node2 = temp;
    }

    Node<T> *n1_prev = node1->prev;
    Node<T> *n1_next = node1->next;
    Node<T> *n2_prev = node2->prev;
    Node<T> *n2_next = node2->next;

    // 区分相邻/非相邻场景处理指针
    if (node1->next == node2) {
        node1->prev = node2;
        node1->next = n2_next;
        node2->prev = n1_prev;
        node2->next = node1;
    } else {
        node1->prev = n2_prev;
        node1->next = n2_next;
        node2->prev = n1_prev;
        node2->next = n1_next;
    }

    // 更新相邻节点的指向
    updateNode(node1);
    updateNode(node2);

    // 统一更新头节点
    if (head == node1) {
        head = node2;
    } else if (head == node2) {
        head = node1;
    }
}

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