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

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param listNode ListNode类 
# @return int整型一维数组
#

class Solution:
    def printListFromTailToHead(self , listNode: ListNode) -> List[int]:
        if not ListNode:
            return []
        
        result = []
        while (listNode):
            result.append(listNode.val)
            listNode = listNode.next
        
        return result[::-1]

• "JZ6_printListFromTailToHead1":
• 通过率：13/13
• 思路：顺序记录链表的值到数组中，倒序输出数组的值。
• 空间O(n) ：O(n) (as result[n])
• 时间O(n)：O(T)=O(T(n))=O(T(1+1+n+n+1))=O(T(2n+3))=O(n)

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param listNode ListNode类 
# @return int整型一维数组
#

class Solution:
    def printListFromTailToHead(self , listNode: ListNode) -> List[int]:
        if not ListNode:
            return []
        
        result = []
        def solutions(Node):
		  if Node:
			if Node.next:
			  solutions(Node.node)
			result.append(Node.val)
        
		solutions(listNode)
        return result

• "JZ6_printListFromTailToHead2":
• 思路：使用递归，从头进，从尾一层层退出
• 问题：ListNode数据大时，不通过。
• 通过率：11/13
• 原因：链表长些时，函数调用层级深，导致函数调用栈溢出。
• 空间O(n^2) =O(n)*n=O(n^2)
• 时间O(T)=O(1)*n=O(n)

递归算法的空间复杂度 = 每次递归的空间复杂度 * 递归深度

递归算法的时间复杂度表达式：O(T) = 每次递归调用计算的时间复杂度 * 递归调用次数

ref:

1. https://blog.csdn.net/golden_life/article/details/123055570
2. https://github.com/youngyangyang04/leetcode-master/blob/master/problems/%E5%89%8D%E5%BA%8F/%E9%80%92%E5%BD%92%E7%AE%97%E6%B3%95%E7%9A%84%E6%97%B6%E9%97%B4%E4%B8%8E%E7%A9%BA%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%88%86%E6%9E%90.md
3. https://bbs.huaweicloud.com/blogs/328978