从尾到头打印链表

Leetcode Link: 剑指 Offer 06. 从尾到头打印链表 - 力扣（LeetCode） (leetcode-cn.com)

题目

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

解法一

思路：最基本的方法。先全都取出来，在反着打印出来。（辅助栈法）

题解：时间 $O (N)$ ，额外空间 $O (N)$

class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        # 数组反转方法求解
        # 等同于依靠栈求解
        que = []
        while(head):
            que.append(head.val)
            head = head.next
        return que[::-1]

解法二

思路：递归

题解：时间 $O (N)$ ，额外空间 $O (N)$

class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        self.nums = []
        self.inRecur(head)
        return self.nums
    
    def inRecur(self, head):
        # 注意这里是不能用self.head = self.head.next
        # 因为那样指针的位置回不来了
        if head == None:
            return # 递归终止条件
        self.inRecur(head.next)
        self.nums.append(head.val)

启发和联系

Python 中对List进行逆序的三种方法

list.reverse()
list[: :-1]
reversed()，inline method, 会将列表逆序的结果存储到迭代器里面，不改变原来的列表，也不创建副本，只会多出迭代器对象所占的空间，相对来说也比较高效。其返回值是一个迭代器，你可以将其理解为一个指针，指向原来的列表。