难度: Medium
Submission
运行时间: 26 ms
内存: 0.0 MB
# """
# This is the ImmutableListNode's API interface.
# You should not implement it, or speculate about its implementation.
# """
# class ImmutableListNode:
# def printValue(self) -> None: # print the value of this node.
# def getNext(self) -> 'ImmutableListNode': # return the next node.
class Solution:
def printLinkedListInReverse(self, head: 'ImmutableListNode') -> None:
node, nodes = head.next, []
while node:
nodes.append(node)
node = node.getNext()
while nodes:
nodes.pop().printValue()
head.printValue()
Explain
该题解的思路是使用一个列表来存储从头节点开始的所有节点，然后逆序打印这些节点的值。首先，题解通过一个while循环遍历链表，并将除了头节点之外的所有节点添加到列表中。之后，使用另一个while循环，从列表中逐个弹出节点，并调用节点的printValue方法来逆序打印节点的值。最后，题解打印了最初的头节点的值，因为头节点没有被添加到列表中。
时间复杂度: O(n)
空间复杂度: O(n)
# ImmutableListNode API interface definition
# class ImmutableListNode:
# def printValue(self) -> None: # print the value of this node.
# def getNext(self) -> 'ImmutableListNode': # return the next node.
class Solution:
def printLinkedListInReverse(self, head: 'ImmutableListNode') -> None:
node, nodes = head.getNext(), [] # Start from the node after head
while node: # Traverse the list and store nodes
nodes.append(node) # Add the current node to the list
node = node.getNext() # Move to the next node
while nodes: # Pop from the list to print values in reverse order
nodes.pop().printValue() # Pop the last node and print its value
head.printValue() # Finally, print the head node's value
Explore
在题解中，头节点的值最后打印的设计是为了简化逻辑和减少操作。如果将头节点也添加到列表中，那么我们需要在循环的开始处处理头节点的添加，这会使代码稍显复杂。另外，由于头节点是链表的固定起始点，直接在最后打印它的值可以保证无论链表如何变化，头节点的处理逻辑都是清晰和一致的，提高了代码的可读性和可维护性。
题解中使用列表来存储节点后逆序打印，虽然简单直观，但确实不是空间最优的方法。一个空间更优的方法是使用递归。递归的方式可以在遍历链表的过程中利用函数调用栈来实现节点的逆序访问，从而避免使用额外的存储空间。然而，递归方法可能会因为链表过长而导致栈溢出。因此，选择哪种方法取决于具体情况，如链表的长度和系统栈的大小。
题解中使用的`pop()`函数默认从列表的末尾移除元素。这是基于Python列表（list）的特性考虑的，因为列表的末尾添加和移除元素的操作是O(1)的时间复杂度，而从列表头部添加或移除元素则通常是O(n)的时间复杂度。因此，使用末尾的`pop()`可以保证每次操作是最高效的，适合实现栈的LIFO（后进先出）特性，从而支持逆序打印的需求。