题解 | #从尾到头打印链表#

从尾到头打印链表

http://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035

算法思想一：辅助数组

解题思路：

1、创建存储链表结点元素的数组 res

2、遍历链表，并同时将遍历的结点存储入数组

3、倒序输出数组结果

图解:

链表：{1，2，3}

步骤	链表	数组
1	遍历结点 1	【1】
2	遍历结点 2	【1，2】
3	遍历结点 3	【1，2，3】
倒序输出数组：【3，2，1】

代码展示：

Python

class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def printListFromTailToHead(self, listNode):
        # write code here
        res = []
        while listNode:
            # 遍历链表，存入数组中
            res.append(listNode.val)
            listNode = listNode.next
        # 数组反向输出
        return res[::-1]

复杂度分析：

时间复杂度O(N)：N是链表的长度，遍历这个链表花费时间

空间复杂度O(N)：额外存储结点数组空间

算法思想二：递归

解题思路：

递归到链表的尾部，再依次将链表结点存入数组中

算法实现：
变量：先创建一个list数组
递归结束条件：当链表结点为null，listNode==null。
结果：list即为逆序排列链表数值后的数组

图解：

代码展示：

JAVA版本

import java.util.ArrayList;

public class Solution {
    ArrayList<Integer> list = new ArrayList();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode!=null){
            // 递归到最后一个链表结点
            printListFromTailToHead(listNode.next);
            // 依次将链表结点元素存入列表
            list.add(listNode.val);
        }
        return list;
    }
}

复杂度分析：

时间复杂度O(N)：N是链表的长度，递归整个链表

空间复杂度O(N)：额外存储空间

算法思想三：栈

解题思路：

1、借助栈的先进后出机制，遍历链表的同时将遍历结点元素入栈

2、遍历结束依次将站内元素出栈

图解：

链表：{1，2，3}

步骤	链表	栈	返回数组
1	遍历结点 1	入栈【1】	【】
2	遍历结点 2	入栈【1，2】	【】
3	遍历结点 3	入栈【1，2，3】	【】
4		3 出栈	【3】
5		2 出栈	【3，2】
6		1 出栈	【3，2，1】

代码展示：

Python版本

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