面试题6：从尾到头打印链表

题目描述

输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

知识点

链表

Qiang的思路V1

看完这道题之后首先想到的就是使用list的insert的方法，因为它可以选择插入到哪个位置，只要我将链表当前的元素插入到list的0号位置，这样遍历一遍list之后就能得到反向的list。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def printListFromTailToHead(self, listNode):
        # write code here
        if listNode is None:
            return []
        l=[]
        while True:
            l.insert(0, listNode.val)
            listNode=listNode.next
            if listNode is None:
                break
        return l

但是这样写不通用，毕竟在C/C++中没有像insert这么好用的方法。所以需要想另一种方法。

Qiang的思路V2

通过分析，在遍历的时候得到的值是从头到尾的，但是现在需要从尾到头，所以想到了栈先进后出的特点。通过栈将遍历的值存起来，然后一次弹出到list中便实现了该功能。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def printListFromTailToHead(self, listNode):
        # write code here
        if listNode==None:
            return []
        stack=[]
        while listNode!=None:
            stack.append(listNode.val)
            listNode=listNode.next
        l=[]
        while stack!=[]:
            l.append(stack.pop())
        return l

Book中的思路

在书中提及的第一种算法恰恰是我想到的第二种方法，另外，书中还提到了一种通过递归解决该问题的方法。主要灵感是递归在本质上就是一个栈结构。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def getResult(self, listNode, res):
        if listNode==None:
            return res
        res=self.getResult(listNode.next,res)
        res.append(listNode.val)
        return res
    def printListFromTailToHead(self, listNode):
        # write code here
        return self.getResult(listNode,[])

但是使用递归的方式解决该问题将会面临着当链表长度过长时的栈溢出问题。所以还是直接用栈来做比较好。

作者原创，如需转载及其他问题请邮箱联系：lwqiang_chn@163.com。
个人网站：https://www.myqiang.top。