LeetCode 面試題06. 從尾到頭打印鏈表【劍指Offer】【Easy】【Python】【鏈表】

問題

力扣

輸入一個鏈表的頭節(jié)點，從尾到頭反過來返回每個節(jié)點的值（用數(shù)組返回）。

示例 1：

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

限制：

0 <= 鏈表長度 <= 10000

思路

解法一

reverse函數(shù)

時間復(fù)雜度: O(n)，n為 head 鏈表長度。
空間復(fù)雜度: O(n)，n為 head 鏈表長度。

Python3代碼

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        # solution one: reverse
        res = []
        while head:
            res.append(head.val)
            head = head.next
        res.reverse()
        return res

解法二

棧

時間復(fù)雜度: O(n)，n為 head 鏈表長度。
空間復(fù)雜度: O(n)，n為 head 鏈表長度。

Python3代碼

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        # solution two: 棧
        stack = []
        while head:  # push
            stack.append(head.val)
            head = head.next
        res = []
        while stack:  # pop
            res.append(stack.pop())
        return res

解法三

遞歸

Python3代碼

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        # solution three: 遞歸
        return self.reversePrint(head.next) + [head.val] if head else []

代碼地址

GitHub鏈接