c - 调试帮助 - 交换双向链表的 2 个节点

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仍然是错误的!

<小时/>

如何解决这个问题？这不是一句简单的话就能解决的，因为有一些特殊情况。

也许可以检测到我描述的特殊情况并为其提供单独的代码(并且不要忘记其他特殊情况)。

编写该代码留给读者作为练习;)