剑指 Offer 06. 从尾到头打印链表python（csdn）————程序.pdf

《从尾到头打印链表》 在计算机科学中，链表是一种常用的数据结构，它由一系列节点组成，每个节点包含数据以及指向下一个节点的引用。在处理链表时，通常的操作包括插入、删除、遍历等。本题讨论的是一个特殊的遍历问题——从尾到头打印链表。 题目描述： 给定一个单链表的头节点`head`，要求编写一个方法`reversePrint`，该方法能按照从链表尾部到头部的顺序打印出链表中的所有元素的值。 题解一：迭代法 我们可以采用迭代的方式来解决这个问题。首先创建一个空列表`numres`，然后从头节点`head`开始遍历链表，将每个节点的值依次添加到`numres`中。当遍历完链表后，`numres`中存储的就是从头到尾的节点值。我们只需要反转`numres`，即可得到从尾到头的顺序。以下是对应的Python代码实现： ```python class Solution: def reversePrint(self, head): numres = [] while head: numres.append(head.val) head = head.next numres.reverse() return numres ``` 题解二：递归法 另一种方法是使用递归。递归的基本思想是将问题分解为更小的子问题，直到子问题变得足够简单可以直接求解。在这个问题中，我们的递归目标是从尾到头打印链表。递归的终止条件是链表为空，此时返回空列表。对于非空链表，我们先对`head.next`进行递归调用，得到从`head.next`到链表尾部的节点值列表，然后将`head`的值添加到这个列表的前面。以下是对应的Python代码实现： ```python class Solution: def reversePrint(self, head): numres = [] if head == None: return numres numres = numres + self.reversePrint(head.next) numres.append(head.val) return numres ``` 在这两种方法中，迭代法的时间复杂度为O(n)，空间复杂度也为O(n)，其中n为链表的长度。递归法的时间复杂度同样是O(n)，但其空间复杂度取决于递归深度，最坏情况下可能达到O(n)。在实际应用中，应根据具体场景选择合适的方法。例如，如果内存限制较宽松，且递归深度不会过大，递归法可以提供简洁的解决方案。而如果内存有限或担心递归深度过大，迭代法可能是更好的选择。