题目
题目描述
输入一个链表的头节点,
从尾到头反过来返回每个节点的值(用数组返回)。
示例
输入: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: |