調試幫助 - 交換雙節點的雙鏈表

Question

請幫我調試一下這個代碼交換雙節點的雙鏈表嗎？我無法找出什麼我做錯了:(

這裏是代碼：

dll* swap_node(dll *head , dll *node1 , dll *node2) { 
    dll *tmp; 
    int flag=0; 

    if(node1->prev!=NULL) { 
     node1->prev->next=node2; 
    } else { 
     flag=1; 
    } 
    if(node1->next!=NULL) { 
     node1->next->prev=node2; 
    } 

    if(node2->prev!=NULL) { 
     node2->prev->next=node1; 
    } 
    if(node2->next!=NULL) { 
     node2->next->prev=node1; 
    } 

    tmp=node1->next; 
    node1->next=node2->next; 
    node2->next=tmp; 

    tmp=node1->prev; 
    node1->prev=node2->prev; 
    node2->prev=tmp; 

    if(flag==1) { 
     head=node2; 
    } 
    return head; 
} 

在此先感謝

Answer 1

假設node1->next == node2 && node2->prev == node1現在讓我們跟蹤：

if(node1->next!=NULL) 
{ 
    node1->next->prev=node2; 
} 

現在node2->prev指向node2本身！

if(node2->prev!=NULL) 
{ 
    node2->prev->next=node1; 
} 

現在node2->next指向node1，現在可以。

回想一下，node1->next仍然指向node2,node2->next指向node1。

tmp=node1->next; // == node2 
node1->next=node2->next; // == node1 (!) 
node2->next=tmp; // == node2 

因此，我們必須node1->next指向node1，並node2->next到node2。顯然是錯誤的。

回想一下node2-> prev指向node2，儘管node1->prev是正確的。

tmp=node1->prev; // correct 
node1->prev=node2->prev; // == node2 
node2->prev=tmp; // correct 

所以node1->prev點node2，這是正確的。

但是node1->next和node2->next仍然是錯誤的！

---

如何解決這個問題？這不是一個要解決的問題，因爲有幾個特例。

也許可以檢測到我描述的特殊情況，併爲其分別設置代碼（並且不要忘記其他特例）。

編寫的代碼被作爲練習留給讀者;）

Answer 2

您的邏輯是行不通的，

1. 如果node2是在雙向鏈表的第一個元素
2. 如果node1和node2是相鄰的。

請仔細閱讀下面給出的更新邏輯。

 

dll* swap_node(dll *head , dll *node1 , dll *node2) 
{ 
    dll* previous_to_node1 = NULL; 
    dll* next_to_node1 = NULL; 
    dll* previous_to_node2 = NULL; 
    dll* next_to_node2 = NULL; 

    if ((node1 == NULL) || (node2 == NULL)) 
     return 0; 

    previous_to_node1 = node1->previous; 
    next_to_node1 = node1->next; 
    previous_to_node2 = node2->previous; 
    next_to_node2 = node2->next; 

    if (previous_to_node1 != NULL) previous_to_node1->next = node2; 
    if (next_to_node1 != NULL) next_to_node1->previous = node2; 
    if (pevious_to_node2 != NULL) previous_to_node2->next = node1; 
    if (next_to_node2 != NULL) next_to_node2->previous = node1; 

    node1->next=next_to_node2;  
    node1->previous=previous_to_node2; 
    node2->next=next_to_node1; 
    node2->previous=previous_to_node1; 

    if (previous_to_node1 == NULL) 
    { 
     return node2; 
    } 
    else if(previous_to_node2 == NULL) 
    { 
     return node1; 
    } 

    return head; 
}