例题５：从尾到头打印单向链表。写段程序，将一个单向链表中的数据从尾到头打印出来，也就是反向打印，并不改变链表本身的结构。

　　分析：反向打印单向链表要解决的问题：由于单向链表只能从前一个节点跟踪到后一个节点，却不能反向。自然地我们会想到用递归算法。

　　递归算法逻辑：如果想打印当前节点的值，首先打印下一个节点的值，也就是打印前先递归到下一个节点，层层递归，直到最后一个节点。这样，只要按照递归完了再打印的逻辑，打印的顺序就颠倒过来了，具体实现看下面的代码。

　　程序代码：

　　运行结果：

　　递归打印虽然简单，但不适合长链的单向链表（爆运行栈）。我们自然会想到，如果尾部也有个指针链向头部，这样不就可以用循环打印了。下面的代码就是每个节点增加一个临时指针，从尾到头，打印后删除这个指针（方法只适合Python）。

　　练习题１：把单项链表的节点依次放入临时列表中，从列表的尾向头循环打印即可实现从尾到头打印单向链表。请设计程序代码测试。

　　例题６：反转一个单向链表。

　　分析：与逆向打印不同，反转一个单向链表是改变链表的结构，使链表中的每个节点的next指针由向后指改为向前指，链表的头指针指向尾节点。这种结构改变同样可以用递归来实现。

　　递归算法分析：可以在链表中写一个方法，传入一个节点，可以通过这个节点找到它指向的下一个节点，然后让下一个节点的next指针指向自己。此方法加入递归即可实现整个链表的反转。

     递归算法逻辑：在让下一个节点的next指针反转之前，先递归调用下一个节点的反转方法。这样层层递归到尾节点，在尾节点反转指针后，前一个节点才能执行反转动作，层层传递到头节点。最后把链表的头指针转指向尾节点。整个反转才算完成。

　　程序代码：

　　运行结果：

　　递归反转同样不适合长链的链表，这个问题其实很简单，只要用一个临时指针缓存节点的下一个节点的后续指针，循环下推，同样操作就可以反转，设置头指针就可以了。

　　程序代码：

　　练习题２：把单项链表的节点依次放入临时列表中，从列表的尾向头循环重构单向链表即可实现反转。请设计程序代码测试。

　　练习题３：利用链表反转，实现从尾到头打印链表。

　　例题７：反转单向链表中索引n~m处节点。

　　分析：指定反转单向链表中第n~m个节点的节点(1≤n≤m≤链表长度)。比如对链表结构1→2→3→4→5，从下标n=1到m=3处做指针反转（表示从下标1到下标3的节点在链表中做结构反转)。最终构造成链表1→4→3→2→5结构（中间结构发生反转后，整体链表结构不被破坏)，如下图所示。

　　递归算法分析如下：

　　(1)临时指针循环到n节点的前一个节点（不是头节点的情况下)。

　　(2)定义一个当前节点编号ii。

　　(3)在ii<m范围内执行后节点指向前节点的反转。

　　(4)当ii==m时，n节点指向m节点的后续节点。

　　(5)n节点的前一个节点指向反转过来的m节点。

　　程序代码：

　　运行结果：

　　与反转整个链表一样，递归也不适合反转的子链太长的情况。我们可以用一些临时变量保存指针，然后用循环法反转。

　　程序代码：

　　练习题４：把单项链表的n~m节点依次放入临时列表中，从列表的尾向头开始循环重构单向链表即可实现反转。请设计程序代码测试。

　　学思营编程课堂基于蓝桥STEM86平台https://www.stem86.com，开展学编程三部曲：Scratch（三年级以前）>>>Python（四年级以后）>>>C++（七年级以后）教育实验活动，任何人可以免费参加，打开https://xuesiying.stem86.com网页注册进入课堂，也可关注本公众号留言。更多课程请打开“学思营”同步网站：http://www.5xstar.com/doc.html

参考资料：

１、《Python算法图解》何韬编著　清华大学出版社