题目
题目描述
输入一个链表的头节点,
从尾到头反过来返回每个节点的值
(用数组返回)。
示例
输入:head = [1,3,2]
输出:[2,3,1]
题解
递归解法
先走到链表末端,回溯时依次将节点元素加入列表。
递推:每次传入head.next
,以head == None
为终止条件,此时返回空列表[]
。
回溯:每次返回当前list + 当前节点元素[head.val]
。
时间复杂度:O(n),遍历链表,递归n次。
空间复杂度:O(n),递归使用O(n)空间。
# Definition for singly-linked list. |
辅助栈
使用Python列表中的reverse方法:
list.reverse()
或list[::-1]
,反向列表中元素。
遍历链表,依次将节点元素push入栈
(使用append方法实现);然后将节点元素pop出栈
(反向)。
时间复杂度:O(n)
空间复杂度:O(n)
class Solution: |