交换双向循环链表上的节点（带指针）

Question

我正在尝试编写一个双向循环链表，但我在交换节点时遇到了一些困难。它适用于除头节点之外的任何节点。我尝试添加一个检查，如果 node1 是 head 没有运气。我哪里做错了？

好吧，我之前说过，但对于除 head 之外的任何其他节点，交换工作正常，我确信这是这里问题的关键，但到目前为止我还看不到。感谢任何帮助。

updateNode(*node) 只需相应地重新排列 prev->next 和 next->prev。

更新： 目前如果node1是头节点，它将node2替换为head->next。 1 2 3 4 5 6 变为 1 6 2 3 4 5.

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) or !contains(node2)) 
        return;

    if (node1 == node2)
        return;
    else if (node2->next == node1 && node1->prev == node2) {
        Node<T> *temp = node1;
        node1 = node2;
        node2 = temp;
    }

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

    if (node1 == head && node2 == head->prev) {
        head->prev = node1;
        head = node2;
        head->next = n1_next;
        head->prev->prev = n2_prev;
    }
    else if (( node1->next == node2 && node2->prev == node1 ) || ( node1->prev == node2 && node2->next == node1 )) {
        node1->prev = n1_next;
        node2->prev = n1_prev;
        node1->next = n2_next;
        node2->next = n2_prev;
    }
    else {
        node1->prev = n2_prev;
        node2->prev = n1_prev;
        node1->next = n2_next;
        node2->next = n1_next;
    }

    updateNode(node1);
    updateNode(node2);
}

Answer 1

一些问题包括：

使用 head->prev = node1 时，节点引用 node1 引用自身，因为此时 head 和 node1 引用同一个节点.
head 在其他情况下也应该改变：当它等于 node1 或 node2 时它应该改变，没有任何其他条件。然后它应该只引用两者中的另一个。
当其中一个节点是头节点时，交换逻辑应该没有任何不同。交换的重新布线应该完全相同。只是（如上所述）如果其中一个是头，则 head 引用应该更新为引用两个中的另一个节点。
如果列表仅包含两个节点（要交换的节点），则无需重新连接。只有 head 引用应该更改。

一些条件可以简化，因为我们可以假设列表是一致的。所以当 node2->next == node1 我们可以默默地假设 node1->prev == node2, ...等等

所以这是您的代码更新：

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

    if (node1 == node2)
        return;
    
    if (node2->next == node1) {
        Node<T> *temp = node1;
        node1 = node2;
        node2 = temp;
    }

    if (node2->next != node1) { // More than 2 nodes in the list
        Node<T> *n1_prev = node1->prev;
        Node<T> *n2_next = node2->next;

        if (node1->next == node2) {
            node1->prev = node1->next;
            node2->next = node2->prev;
        } else {
            node1->prev = node2->prev;
            node2->next = node1->next;
        }
        node2->prev = n1_prev;
        node1->next = n2_next;

        updateNode(node1);
        updateNode(node2);
    }
    // If head was swapped, it should reference the other one now
    if (head == node1)
        head = node2;
    else if (head == node2)
        head = node1;
}

交换双向循环链表上的节点（带指针）

Swap nodes (with pointers) on doubly circular linked list

c++

linked-list

circular-list

doubly-linked-list