题目描述

[牛客网]

06. 从尾到头打印链表

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

解法 1:正常遍历

Emmmmmm... 就正常遍历。

假设链表长度为 $n$,那么

  • 时间复杂度为 $O(n)$,遍历一遍;
  • 空间复杂度为 $O(n)$,保存从头到尾的结果。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # 要求:
    # 1. 返回从尾部到头部的值序列,例如 [1, 2, 3]
    def printListFromTailToHead(self, listNode):
        ret = []
        while listNode is not None:
            ret.append(listNode.val)
            listNode = listNode.next
        return ret[::-1]
  • 运行时间:29ms
  • 占用内存:5732k

解法 2:链表结点栈

可以维护一个栈,遍历链表然后把结点压栈,遍历完了再出栈输出。其实跟解法 1 类似,有点脱裤子放屁的感觉。

假设链表长度为 $n$,那么

  • 时间复杂度为 $O(n)$,遍历一遍压栈,再遍历一遍出栈;
  • 空间复杂度为 $O(n)$,保存完整大小的结点栈。

代码略。

解法 3:递归

既然能用栈,自然能用递归,虽然更麻烦,而且还有函数调用栈溢出的风险。

代码略。