首页 > 代码库 > 单链表反转(2)

单链表反转(2)

今天会介绍另外一种反转单链表的方法,对于单链表反转这一类的算法,最重要的思想就是用临时变量来记住需要记住的节点。一个不够,那就用两个,或者用三个临时变量。

这次还是以图表来表现算法的过程,不同于上一篇,这次的头节点使用链表中的第一个节点。

该方法的思想就是遍历每个节点,将其插入到第一个节点之后。

如下图为链表的初始状态:

技术分享

为了不断链,先将 P2 的后驱节点指向 P3 的后驱节点。

技术分享

将P3插入 P1 和 P2 之间,也就是 将 P1 的后驱指向 P3.将 P3 的后驱指向 P2

技术分享

P3 指向 P2 的后驱节点

技术分享

一直重复上述的操作,知道P2后驱的后驱为空,这时候的单链表结构如图所示:

技术分享

这时候反转单链表的主要工作已经做完。但是 P2 的后驱还没有指向以前的第一个节点,这时候我们需要做的是把 P2的后驱指向 P1,P1 的后驱指向空节点即可。

单链表反转(2)