python算法-004逆序输出链表但是不改变链表结构

志士惜日短，愁人知夜长。——晋.傅玄《杂诗》

努力学习吧！留给我们的时间不多了！
先补上昨天忘记说的，昨天的插入法相比于递归法和就地逆序法，既不需要多余的空间来保存额外指针，也不要需要递归调用函数，效率过更高。
下面是今天的题目，比较简单

---

题目：给定链表head->1->2->3->4->5->6->7->8,编写算法，输出8，7，6，5，4，3，2，1；但是不能改变链表结构。即在输出链表后，链表依然是head->1->2->3->4->5->6->7->8。

---

今天的题目不在是逆序链表了，而是逆序输出了。上来一看可能有点懵，先来看一下如何逆序输出链表，如果不考虑后面的要求，我们很容易想到先把链表逆序，然后在顺序输出，那么输出结果就是逆序输出了。逆序链表的方法上面给出了三种，各有优缺点。那么我们要怎么逆序输出链表而不改变链表结构呢？下面给出的方法是——递归法。

递归法在前面已经讲过了，今天在来复习一下，顺便解决这个问题。我们说递归程序有两个要素：递归定义和递归终止条件。先来分析下：要输出：head->1->2->3->4->5->6->7->8的逆序，就要先输出2->3->4->5->6->7->8的逆序然后输出第一个节点，就可以实现输出逆序链表了；但是要输出2->3->4->5->6->7->8的逆序，就要先输出3->4->5->6->7->8的逆序，然后输出2；同理直到最后一个元素8，直接输出便是逆序，然后递归输出7，6，5……。这就实现了逆序输出，而且我们并没有改变任何一个节点的next域或者data域，也就没有改变链表结构。经过以上分析：递归定义为：先输出除当前节点外的子链表的逆序，然后输出当前节点；递归终止条件为：当链表只剩一个元素或者链表为空。你们可能感受不到链表结构是否改变。下面用代码实现，我们一起来看看是否能满足题目的要求：
先构造链表,这之前讲了——python算法-002单链表逆序递归法里有解释：

#先构造节点对象
class LNode:
    """
    定义链表对象
    """
    def __init__(self, x):
        self.data = x
        self.next = None
#构造链表函数
def creatLink(x):
    i = 1
    head = LNode(None)
    tmp = None
    cur = head
    while i <= x:
        tmp = LNode(i)
        cur.next = tmp
        cur = tmp
        i += 1

这里开始实现今天的算法：

def ReversePrint(head):
    """
    逆序输出但不改变链表结构
    """
    #先判断链表是否为空，是则直接返回
    if head.next is None or head is None:
        return
    firstNode=head.next # 用来遍历链表，也是子链表的第一个节点
    ReversePrint(firstNode) # 递归调用子链表
    print(firstNode.data) # 输出当前遍历节点的data
    return head # 用于判断链表结构是否变化

---

这就是实现算法的代码，相比昨天的短很多，相信很容易理解吧！下面来看看运行效果：
主程序：

if __name__ == '__main__':
    head=creadLink(8)
    #先看一下链表的结构
    print("BeforeReverse:")
    cur = head.next
    while cur != None:
        print(cur.data)
        cur = cur.next
    #逆序输出链表
    print("ReversePrint:")
    head = ReversePrint(head)
    #然后看看逆序后的链表是否有变化
    print("BeforeReverse:")
    cur = head.next
    while cur != None:
        print(cur.data)
        cur = cur.next

程序输出结果如下：

输出结果

全部代码：

#先构造节点对象
class LNode:
    """
    定义链表对象
    """
    def __init__(self, x):
        self.data = x
        self.next = None
#构造链表函数
def creatLink(x):
    i = 1
    head = LNode(None)
    tmp = None
    cur = head
    while i <= x:
        tmp = LNode(i)
        cur.next = tmp
        cur = tmp
        i += 1
    return head
def ReversePrint(head):
    """
    逆序输出但不改变链表结构
    """
    #先判断链表是否为空，是则直接返回
    if head.next is None or head is None:
        return
    firstNode=head.next # 用来遍历链表，也是子链表的第一个节点
    ReversePrint(firstNode) # 递归调用子链表
    print(firstNode.data) # 输出当前遍历节点的data
    return head # 用于判断链表结构是否变化
if __name__ == '__main__':
    head=creatLink(8)
    #先看一下链表的结构
    print("BeforeReverse:")
    cur = head.next
    while cur != None:
        print(cur.data)
        cur = cur.next
    #逆序输出链表
    print("ReversePrint:")
    head = ReversePrint(head)
    #然后看看逆序后的链表是否有变化
    print("BeforeReverse:")
    cur = head.next
    while cur != None:
        print(cur.data)
        cur = cur.next

---

好的，今天的算法就到这里。这里先跟大家道个歉。事情是这样的：我在写文章的时候，代码本来我是自己写好的，但是注释并没有现在这么多，而且有些细节上的东西我没注意到，需要改动，所以会在辨析的时候增改一些东西，难免会有多个空格，换个行写注释啥的。要命的地方来了！ Python中用缩进来划分代码块，看起来很美观，事实上也很美观，但是混用空格和Tab键，是万万不能的，所以写代码时一定注意只用一种！！！但是我在前面几篇文章中并没有注意到这点（真香！），今天的代码直接复制应该就能运行（但是我不建议这么做）。这导致同学们复制下来不能直接运行，还会报一些奇怪的错误……对不起，是我错了！同时也不建议你们直接复制，自己写写会发现很多有趣的东西的。前面的几篇我也不会去改，留给你们慢慢改吧！但是在以后的文章不会出现这样的情况了。

还有一点，在我的github(网站是英文的，手机端点viewcode就能看到了，电脑上直接能看到)，上面的是我自己写的能直接运行的代码，题目是对应的，但是代码可能会稍微有一点出入。上面的题目要多一些，但是没有这么详细的解释，想学习的，可以自己研究研究(好东西)

莫道谗言如浪深，莫言迁客似沙沉。
千淘万漉虽辛苦，吹尽狂沙始到金。
——刘禹锡 《浪淘沙》

加油！！