当前位置:C++技术网 > 精选软件 > [链表节点位置互换]追问解答:链表前后单元用指针实现调换

[链表节点位置互换]追问解答:链表前后单元用指针实现调换

更新时间:2016-08-11 21:30:19浏览次数:1+次

经过整理追问得到的提问描述,重新理顺了一下链表开始状态和结果状态,如下图所示:

提问的用户给的原图:

原提问文章地址:链表前后单元用指针实现调换

C++技术网解答:

    两个节点交换,实际上至少有两种方式实现,一个是前接法,一个是后接法。前接法指的是,按照结果的排列,先将结果的排列的前面一个固定好n1-n3,而后接法,则是先将结果排列的节点接好n2-n4。

前接法:


第一步:断开n1-n2,将n1-n3链接起来。这是结果状态前面的两个节点。结果图如下:

第二步:将n2-n4连接起来,此时因为p2可以得到n3的节点的下一个节点地址。结果如下图所示:

第三步:利用p1和p2指针,和轻松将n3-n2拼接起来。

点评:在这种方法中充分利用了p2,所以无需增加额外的临时指针。代码如下图:


p1->next=p2->next;//n1指向n3
p2->next=p1->next->next;//n2指向n4
p1->next->next=p2;//n3指向n2


后接法:

第一步:因为先要将n2-n4连接起来,这样会导致n3节点的地址丢失,所以要用一个临时指针pTemp来存储n3地址。

第二步:将n2-n4连接起来。此时有pTemp指向n3,所以没有丢失n3地址。

第三步:在这一步,你既可以连接n3-n2,也可以连接n1-n3,因为每一个节点都有指针,随便玩。

第四步:完成最后一步的拼接。

点评:这一种方法明显浪费了指针,所以后面可以随便拼接。多了一个临时指针,所以不如第一个方法好。而且步骤变多了一个。下面只给其中一条实现路线的代码:


pTemp=p2->next;//pTemp临时n3节点地址
p2->next=pTemp->next;//n2指向n4
pTmp->next=p1->next;//n3指向n2
p1->next=pTemp;//n1指向n3


    解决这个置换问题,要时刻清楚各个节点的next指向了哪里。需要额外的指针的时候,往往是节点没办法利用现有的指针和节点存储的值找到了。在思考思路 时,建议先画好开始和结果的两个链表序列,这样再想的时候,根据从前到后,或者从后到前的顺序来思考实现,思路会很清晰,而不要在一个图中滑来滑去,这样 容易混乱。如果步骤多,记不住,最好像文中一样,把每一步的状态画出来,这样有指向的就能够访问,没有指向的就丢失了。