交换双向链表

Question

好吧。

因此，我一直在尝试实现一个具有交换函数的双向链表。

我在网上找到了许多解释如何做到这一点的网站-几乎所有的网站(包括一些来自Stack Overflow的网站)，都会在评论中开始关于实现是否正确的争论。我已经尝试了几个，但都没有用。换句话说，我找不到这个算法的一个明确版本。

我尝试了至少4-5种与我在网上找到的算法不同的算法，以及一些我试图自己排序的算法，但我总是遇到元素排序不正确的问题。我完全束手无策。

这是我尝试过的最新版本，它不起作用：

template <typename T>
void PriorityQueue<T>::swap(Node * n1, Node * n2){
    if(n1 == n2)
        return;
    if(n1 == 0 || n2 == 0){
        std::cout << "\nPRIORITYQUEUE ERROR: Trying to swap with non-existent node\n";
        return;
    }

    Node * temp = new Node;

    temp->prev = n1->prev;
    temp->next = n1->next;

    n1->prev = n2->prev;
    n1->next = n2->next;

    n2->prev = temp->prev;
    n2->next = temp->next;

    if(n1->next != 0)
        n1->next->prev = n2;
    if(n1->prev != 0)
        n1->prev->next = n2;
    if(n2->next != 0)
        n2->next->prev = n1;
    if(n2->prev != 0)
        n2->prev->next = n1;

    delete temp;

}

我非常沮丧。有没有人，请，请帮我一把，给我一个完整的，有效的算法。不是链接到一个带有损坏的算法的页面，并评论如何修复它(我现在已经尝试了几次)，而只是算法。它甚至不需要是代码，只需要一个算法。请。我已经厌倦了尝试解决这个问题，所以在这个项目上落后于计划，如果有人能一劳永逸地帮助我解决这个问题，我将永远感激不尽。

Answer 1

你的问题在最后几行。我更正了它们：

if(n1->next != 0)
    n1->next->prev = n1; // n2;
if(n1->prev != 0)
    n1->prev->next = n1; // n2;
if(n2->next != 0)
    n2->next->prev = n2; // n1;
if(n2->prev != 0)
    n2->prev->next = n2; // n1;

在函数的开头，有两个节点n1和n2，它们的指针指向其他元素n1p、n1n、n2p和n2n。

<-| p |  <-| p |  <-| p |
  |n1p|    | n1|    |n1n|
  | n |->  | n |->  | n |->

<-| p |  <-| p |  <-| p |
  |n2p|    | n2|    |n2n|
  | n |->  | n |->  | n |-> 

在第一部分中，使用temp变量交换n1和n2节点的指针。所以你会遇到这样的情况。

<-| p |  <-| p |  <-| p |
  |n1p|    | n2|    |n1n|
  | n |->  | n |->  | n |->

<-| p |  <-| p |  <-| p |
  |n2p|    | n1|    |n2n|
  | n |->  | n |->  | n |->

您的问题是您错误地更改了n1p、n1n、n2p和n2n的指针。看看example中简化的Node类和正确的swap函数。