我的双链表交换功能有什么问题吗？

Question

我有一个用于交换2个节点的函数：

void swap(Node<T>* a, Node<T>* b) {
    if(a->m_prev)
        a->m_prev->m_next = b;
    if(b->m_prev)
        b->m_prev->m_next = a;
    if(a->m_next)
        a->m_next->m_prev = b;
    if(b->m_next)
        b->m_next->m_prev = a;

    Node<T>* temp;
    temp = a->m_prev;
    a->m_prev = b->m_prev;    
    b->m_prev = temp;
    temp = a->m_next;
    a->m_next = b->m_next;    
    b->m_next = temp;
}

然而，当与我的递归选择排序一起使用时：

void selectionSort(Node<T>* head) {
    if(next(head) == NULL) {
        return;
    }
    Node<T>* minimum = min(head);

    swap(head,minimum);

    selectionSort(minimum->m_next);
}

在排序进行到一半时，它会将我节点的下一个指针设置为NULL，然后当我打印列表时，它会正确地排序到该值，但由于指针被错误地设置为NULL，其余的指针将丢失。

我查了一下然后：

我的初始列表是正确的，没有错误连接的节点。

我的swap函数只在非null有效节点上调用。

所以我责怪交换功能。它有什么问题吗？

Answer 1

这应该行得通。

void swap(Node<T>* a, Node<T>* b) {

    if ( a == b )
    {
       return;
    }

    Node<T*> oldANext = a->m_next;
    Node<T*> oldAPrev = a->m_prev;
    Node<T*> oldBNext = b->m_next;
    Node<T*> oldBPrev = b->m_prev;

    // Special case when b is the next of a.
    if ( a->m_next == b )
    {
       a->m_next = oldBNext;
       a->m_prev = b;
       b->m_next = a;
       b->m_prev = oldAPrev;

       if ( oldAPrev )
          oldAPrev->m_next = b;
       if ( oldBNext )
          oldBNext->m_prev = a;
    }
    // Special case when b is the prev of a.
    else if ( a->m_prev == b )
    {
       a->m_prev = oldBPrev;
       a->m_next = b;
       b->m_prev = a;
       b->m_next = oldANext;

       if ( oldANext )
          oldANext->m_prev = b;
       if ( oldBPrev )
          oldBPrev->m_next = a;
    }
    // When a and b are not related.
    else
    {
       a->m_next = oldBNext;
       a->m_prev = oldBPrev;
       b->m_next = oldANext;
       b->m_prev = oldAPrev;

       if ( oldANext )
          oldANext->m_prev = b;
       if ( oldAPrev )
          oldAPrev->m_next = b;
       if ( oldBNext )
          oldBNext->m_prev = a;
       if ( oldBPrev )
          oldBPrev->m_next = a;
    }
}

Answer 2

只需交换节点中的值，即可避免指针灾难

Answer 3

我认为问题发生在a在列表中与b相邻时。例如，如果b-

b->prev->next = a; 

是相当于

a->next = a;

这显然不是你想要的。

下面是一些如何解决在双链表中交换节点问题的技巧。要交换的节点A和B将被称为内部节点。列表中的其他节点是外部节点。靠近A和/或B的外部节点应指定为W、X、Y和Z。远离A和B的外部节点应指定为省略号。交换内部节点时，将有2个、3个或4个外部节点参与交换，如下所示

case 1: widely separated (four external nodes)      ... W A X ... Y B Z ...
case 2: separated by one (three external nodes)     ... W A X B Z ...
case 3: adjacent (two external nodes, A first)      ... W A B Z ...
case 4: adjacent (two external nodes, B first)      ... W B A Z ...

应该可以用一组代码处理前两种情况（在情况2中，X同时连接到a和B的事实应该不会对交换实现产生影响）。如果B在A之前，则可以通过交换函数参数来处理最后两种情况，这样变量A始终指向第一个节点，变量B始终指向第二个节点。因此，这四种情况被简化为两种情况，建模为

cases 1&2:   ... W A X ... Y B Z ...
cases 3&4:   ... W A B Z ...

在案例1中

我建议用铅笔和纸坐下来，首先确定需要更新的指针，然后确定每个指针的最终值。知道了这一点，编码部分应该很简单。