03 从尾到头打印链表

题目描述

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

示例：

输入: 1->2->3->4->5
输出: [5, 4, 3, 2, 1]

解题思路

方法一：使用栈

核心思想：利用栈的"后进先出"特性，遍历链表入栈，再依次出栈。

方法二：递归

核心思想：递归到链表末尾，返回时依次添加节点值。

方法三：翻转列表

核心思想：先遍历链表存入列表，再翻转列表。

时间复杂度：O(n) 空间复杂度：O(n)

Python 实现

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


# 方法一：使用栈
def print_list_from_tail_to_head_stack(head):
    """
    使用栈从尾到头打印链表
    """
    stack = []
    p = head
    while p:
        stack.append(p.val)
        p = p.next

    result = []
    while stack:
        result.append(stack.pop())
    return result


# 方法二：递归
def print_list_from_tail_to_head_recursive(head):
    """
    使用递归从尾到头打印链表
    """
    if not head:
        return []
    return print_list_from_tail_to_head_recursive(head.next) + [head.val]


# 方法三：翻转列表
def print_list_from_tail_to_head_reverse(head):
    """
    遍历后翻转列表
    """
    result = []
    p = head
    while p:
        result.append(p.val)
        p = p.next
    return result[::-1]


# 辅助函数：创建链表
def create_linked_list(arr):
    if not arr:
        return None
    head = ListNode(arr[0])
    p = head
    for val in arr[1:]:
        p.next = ListNode(val)
        p = p.next
    return head


# 测试代码
if __name__ == "__main__":
    # 创建链表 1->2->3->4->5
    head = create_linked_list([1, 2, 3, 4, 5])

    print(print_list_from_tail_to_head_stack(head))     # [5, 4, 3, 2, 1]
    print(print_list_from_tail_to_head_recursive(head)) # [5, 4, 3, 2, 1]
    print(print_list_from_tail_to_head_reverse(head))   # [5, 4, 3, 2, 1]

图解

原链表: 1 -> 2 -> 3 -> 4 -> 5 -> None

使用栈:
遍历入栈: [1, 2, 3, 4, 5]
依次出栈: 5, 4, 3, 2, 1
结果: [5, 4, 3, 2, 1]

递归过程:
print_list(1) → print_list(2) + [1]
print_list(2) → print_list(3) + [2]
print_list(3) → print_list(4) + [3]
print_list(4) → print_list(5) + [4]
print_list(5) → [] + [5] = [5]
回溯: [5, 4, 3, 2, 1]