剑指Offer[06]-从尾到头打印链表

题目

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

示例:

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

python代码:

class Solution(object):
    def reversePrint(self, head):
        """
        :type head: ListNode
        :rtype: List[int]
        """
        out_l = []
        while head:
            out_l.append(head.val)
            head = head.next
        return out_l[::-1]

上述解法很常规,因为我们知道链表的特殊性(只能知道当前节点的信息,以及一个指向下一个节点的指针),所以我们要想得到每个节点的值,必须要遍历。正向遍历后,再将得到的列表顺序取反,就是最终的结果。

  • 思考
    >我们想象一下遍历节点以及存入列表的过程,是不是跟一种数据结构相似?是的,就是栈。为什么可以理解为栈呢?因为链表只能正向遍历,而列表最后是要反过来的,符合先进后出的特点。

我们这里使用递归来模拟压栈过程(递归的遍历具备栈的特点)

class Solution(object):
    def reversePrint(self, head):
        """
        :type head: ListNode
        :rtype: List[int]
        """
        out_l = []
        def insert(node):
            if node:
                insert(node.next)
                out_l.append(node.val)
        insert(head)
        return out_l

当insert达到最后一个节点时,才开始执行out_l.append(node.val),然后依次退出函数,并同步将node.val按照倒序放入list中。

发表评论

电子邮件地址不会被公开。