如何爲雙向鏈表創建交換函數？

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等其他指針也一樣。