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
指向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
仍然是错误的!
怎么解决这个? 这不是一个单行解决方案,因为有几个特殊情况。
也许检测我描述的特殊情况并为它设置单独的代码(并且不要忘记其他特殊情况)。
编写该代码留给读者练习;)
你的逻辑不起作用,
- 如果
node2
是双向链表中的第一个元素 - 如果
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)) 返回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; } 回头; }