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


一、题目

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

示例 1:

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

限制:

0 <= 链表长度 <= 10000

二、思路

1. 列表反转

对链表进行遍历,将遍历到的节点值依次添加到一个数组中,然后将数组反转并返回。

2. 递归

head.next传入递归,将返回结果加上当前节点head的值作为结果返回。

三、代码

1. 列表反转

# 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]:
        res = []
        while head:
            res.append(head.val)
            head = head.next

        return res[::-1]

2. 递归

# 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]:
        return self.reversePrint(head.next) + [head.val] if head else []

四、表现

method 运行时间 表现 内存消耗 表现
1. 列表反转 48ms 72.43% 15.1MB 27.92%
2. 递归 136ms 14.03% 22.8MB 7.32%

文章作者: Arvin He
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Arvin He !
评论
  目录