如何为双链表创建交换函数

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内部的指针。所以当你覆盖它们时，你就有麻烦了。

现在，图片中的"之前"one_answers"之后"项目才是你真正想要的。把它们复制出来，然后进行逻辑运算要容易得多。看看下面的代码有多清晰：

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）也是如此。