JZOffer 06-从尾到头打印链表-简单-链表

剑指 Offer 06. 从尾到头打印链表

Question

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

Example 1:

输入：head = [1,3,2] 输出：[2,3,1]

提示：

• 0 <= 链表长度 <= 10000

Approach 1: 栈

栈的特点是后进先出，即最后压入栈的元素最先弹出。考虑到栈的这一特点，使用栈将链表元素顺序倒置。从链表的头节点开始，依次将每个节点压入栈内，然后依次弹出栈内的元素并存储到数组中。

• 创建一个栈，用于存储链表的节点

• 创建一个指针，初始时指向链表的头节点

• 当指针指向的元素非空时，重复下列操作：

  • 将指针指向的节点压入栈内
  • 将指针移到当前节点的下一个节点

• 获得栈的大小 size，创建一个数组 print，其大小为 size

• 创建下标并初始化 index = 0

• 重复 size 次下列操作：

  • 从栈内弹出一个节点，将该节点的值存到 print[index]

  • 将 index 的值加 1

• 返回 print

import math
from enum import Enum
import bisect
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def stringToListNode(input):
    # Now convert that list into linked list
    dummyRoot = ListNode(0)
    ptr = dummyRoot
    for number in input:
        ptr.next = ListNode(number)
        ptr = ptr.next
    ptr = dummyRoot.next
    return ptr

def listNodeToString(node):
    if not node:
        return "[]"
    result = ""
    while node:
        result += str(node.val) + ", "
        node = node.next
    return "[" + result[:-2] + "]" # 最后一个逗号不输出

class Solution:
    def reversePrint(self, head: ListNode):
        resList = []
        while head:
            resList.append(head.val)
            head = head.next
        return resList[::-1]

def main():
    head = stringToListNode([1,3,2])
    solution=Solution().reversePrint(head)
    print(solution)

if __name__ == "__main__":
    main()

复杂度分析

• 时间复杂度：O(n)。正向遍历一遍链表，然后从栈弹出全部节点，等于又反向遍历一遍链表。

• 空间复杂度：O(n)。额外使用一个栈存储链表中的每个节点。