剑指offer刷题记录4--从头到尾打印链表

该系列博客内容主要是《剑指Offer》中的经典题目,结合在刷题过程中见到的一些精彩的解题过程,从而在这里记录下来。代码以Python3实现。
剑指offer刷题记录4--从头到尾打印链表
文章图片

解法1
剑指offer刷题记录4--从头到尾打印链表
文章图片

剑指offer刷题记录4--从头到尾打印链表
文章图片
剑指offer刷题记录4--从头到尾打印链表
文章图片
对于这里递归的用法,起初并不是很清楚,看了答主给出的一段Java的代码,才恍然大悟。
剑指offer刷题记录4--从头到尾打印链表
文章图片

这里需要注意的是,因为recur(head.next)在前面,所以这行代码会一直运行下去,直到链表的最后端null,这里的recur(head.next)也是递归调用。之后再执行回溯即返回的时候,前面的函数才算执行完毕。这儿可能会有一个疑问,在返回的时候不就相当于退出这个recur函数了吗,为啥还会继续执行下面的tmp.add(head.val)?这正是递归函数的特点,当返回的时候, 返回的是最下层的 recur() ,而上层的 recur() 并没有退出,因此上层的 recur() 就会执行下面的 tmp.add(head.val)。
关于递归,我的理解是,递归的本质是通过函数体来进行的循环,只不过是通过循环体来调用自己来进行所谓的循环,因为最开始的计算机语言本质是汇编,没有什么循环一说。当要执行某个重复指令的时候,你就只能不断地反复跳到之前的那段指令。
递归:Recursion
1、从前有座山
2、山里有座庙
3、庙里有个和尚讲故事
4、返回1
这个就是所谓的递归。
在这里需要注意的是,当进到每一层递归的时候,相当于进入到了一个新的世界或者是互不干扰的世界,在里面做一些事情,然后再到下一层再做某些事情。如果要返回的话,只能是一层一层的返回。
剑指offer刷题记录4--从头到尾打印链表
文章图片

这里大概有四步:1)递归终结条件,不写终结条件会进入死循环 ;2)处理当前层逻辑;3)进入到下一层;4)递归结束,清理当前层。
【剑指offer刷题记录4--从头到尾打印链表】用一个比较通俗的说法来解释递归和回溯:
我们在路上走着,前面是一个多岔路口,因为我们并不知道应该走哪条路,所以我们需要尝试。尝试的过程就是一个函数。
我们选择了一个方向,后来发现又有一个多岔路口,这时候又需要进行一次选择。所以我们需要在上一次尝试结果的基础上,再做一次尝试,即在函数内部再调用一次函数,这就是递归的过程。
这样重复了若干次之后,发现这次选择的这条路走不通,这时候我们知道我们上一个路口选错了,所以我们要回到上一个路口重新选择其他路,这就是回溯的思想。
剑指offer刷题记录4--从头到尾打印链表
文章图片

剑指offer刷题记录4--从头到尾打印链表
文章图片

完整实现
剑指offer刷题记录4--从头到尾打印链表
文章图片

参考链接

    推荐阅读