题解 | #从尾到头打印链表#

编程打卡第二天

方法1：把链表的数值存在list里，再反转

class Solution:
    def printListFromTailToHead(self , listNode: ListNode) -> List[int]:
        # write code here
        result = []
        l = listNode
        while l:
            result.append(l.val)
            l = l.next
        return result[::-1]

Key point:

1.listNode循环体常用while listNode来替代for i in range(len(list))

2.类似于list的list[i]的表达是listNode.val

3.执行链表下一个的语句是listNode.next

方法2：递推法

motivation：因为是反转，所以考虑用递推

import sys
#设置递归深度
sys.setrecursionlimit(100000) 
class Solution:
    def recursion(self, head: ListNode, res: List[int]):
        if head:
            #先往链表深处遍历
            self.recursion(head.next, res) 
            #再填充到数组就是逆序
            res.append(head.val) 
    def printListFromTailToHead(self , listNode: ListNode) -> List[int]:
        res = []
        #递归函数打印
        self.recursion(listNode, res) 
        return res

留个尾巴，看的不是很懂，递归果然是一看就会一写就废

方法3：栈

motivation： 栈的特征是先进后出，但要注意和.pop()连用

class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def printListFromTailToHead(self, listNode):
        # write code here
        if not listNode:
            return []
        # 辅助栈
        stack = []
        res = []
        while listNode:
            stack.append(listNode.val) # 进栈
            listNode = listNode.next
        while stack:
            res.append(stack.pop()) # 出栈
        return res

参考资料：

https://blog.nowcoder.net/n/58b4eb98a9f84d0a9cddb9f25122ed56

https://blog.nowcoder.net/n/b4cdfe9e3be84c31a35d3dc80862d082