c++ - 如何为双向链表创建交换函数？

Question

我在为双向链表创建交换函数时遇到问题。我想简单地“重新连接”列表而不更改任何值(我知道这很容易)。我试图创建这个临时项目来保存 back<-p->front这样我就可以将 q = 设置为前后，但临时项随 p 一起更改。我如何在没有临时项目的情况下交换这些项目，或者如何让我的临时项目正常运行。

void DLinkedList::swap(Item *p, Item *q)
{
    Item* temp = p;
    p->next = q->next;
    p->pre = q->pre;
    if (p->next != NULL)
        p->next->pre = p;
    if (q->next != NULL)
        q->next->pre = q;
    q->next = temp->next;
    q->pre = temp->pre;
    if (p->pre != NULL)
        p->pre->next = p;
    if (!q->pre == NULL) {
        q->pre->next = q;
    }
    cout << "- The items " << p->val << " & " << q->val << " were swapped -" << endl;
}

Answer 1

这是图片形式的情况:

+----------+       +----------+       +----------+
| before_p |  <->  |     p    |  <->  | after_p  |
+----------+       +----------+       +----------+

+----------+       +----------+       +----------+
| before_q |  <->  |     q    |  <->  | after_q  |
+----------+       +----------+       +----------+

您遇到的问题是，将 temp 指针保存到 p 并不会实际复制 p 中的指针。因此，当您覆盖它们时，您就有麻烦了。

现在，图片中的那些“之前”和“之后”项目才是您真正想要的。将它们复制出来然后执行逻辑要容易得多。看看下面的代码是多么清晰:

Item * before_p = p->pre;
Item * before_q = q->pre;
Item * after_p = p->next;
Item * after_q = q->next;

// Relink before and after nodes
if( before_p ) before_p->next = q;
if( before_q ) before_q->next = p;
if( after_p ) after_p->pre = q;
if( after_q ) after_q->pre = p;

// Relink nodes themselves
p->pre = before_q;
q->pre = before_p;
p->next = after_q;
q->next = after_p;

您可能还需要在做任何事情之前进行健全性测试:

if( p == q || !p || !q ) return;

最后，如果您在某处维护一个指向列表头部的指针，而这恰好是交换的项目之一，请不要忘记在之后更新它*。

if( head == p ) head = q;
else if( head == q ) head = p;

(*) 同样适用于其他指针，例如 tail。