交换双循环链表上的节点(带指针)

Question

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

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

updateNode(*node)只需相应地重新排列上一个>下一个和下一个>上一个。

更新：目前，如果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;
}