debug help – 交换双链表的2个节点

你能帮我调试一下这个代码来交换双链表的两个节点吗? 我无法弄清楚我做错了什么:(

这是代码:

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; } 

提前致谢

假设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指向node1node2->next指向node2 。 显然错了。

回想一下,node2-> prev指向node2 ,尽管node1->prev是正确的。

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

所以node1->prev指向node2 ,这是正确的。

但是node1->nextnode2->next仍然是错误的!


怎么解决这个? 这不是一个单行解决方案,因为有几个特殊情况。

也许检测我描述的特殊情况并为它设置单独的代码(并且不要忘记其他特殊情况)。

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

你的逻辑不起作用,

  1. 如果node2是双向链表中的第一个元素
  2. 如果node1node2相邻。

请更好下面给出的更新逻辑。


 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))
         返回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_to_node2;    
     node1->先前= previous_to_node2;
     node2->下一= next_to_node1;
     node2->先前= previous_to_node1;

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

    回头;
 }