《计算思维与算法入门》 —2.4.4 单向链表的反转

2.4.4  单向链表的反转

了解单向链表节点的删除和添加之后，大家会发现在这种具有方向性的链表结构中增删节点是相当容易的一件事。而要从头到尾输出整个单向链表也不难，但若要反转过来输出单向链表，则需要某些技巧。我们知道单向链表中的节点特性是知道下一个节点的位置，可是却无从得知它的上一个节点的位置。如果要将单向链表反转，就必须使用三个指针变量，如图2-33所示。

图2-33  单向链表的反转

在算法invert(X) 中，我们使用了p、q、r三个指针变量，它的运算过程如下：

（1）执行while循环前，如图2-34所示。

图2-34  执行while循环前链表和各个指针变量的情况

（2）第一次执行while循环，如图2-35所示。

图2-35  第一次执行while循环后链表和各个指针变量的情况

（3）第二次执行while循环，如图3-36所示。

图2-36  第二次执行while循环后链表和各个指针变量的情况

当执行到p = NULL时，单向链表就整个反转过来了。