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

我有一个用于交换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，因此其余部分丢失了。

我检查并:

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

仅使用非空有效节点调用我的交换函数。

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

最佳答案

我认为当a与列表中的b相邻时，就会出现问题。例如，如果b->prev指向a(意味着a在列表中的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＆2中，内部节点上有4个指针需要更新，而外部节点上有4个指针需要更新。在情况3＆4中，内部节点上有4个指针需要更新，而外部节点上只有2个指针需要更新。

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