题目描述

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

思路

1、非递归

listNode 是链表，只能从头遍历到尾，但是输出却要求从尾到头，这是典型的”先进后出”，我们可以想到栈！ArrayList 中有个方法是 add(index,value)，可以指定 index 位置插入 value 值所以我们在遍历 listNode 的同时将每个遇到的值插入到 list 的 0 位置，最后输出 listNode 即可得到逆序链表。

  • 时间复杂度：O（n2）

  • 空间复杂度：O（n）

    1. import java.util.ArrayList;
    2. public class Solution {
    3.   public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    4.       ArrayList<Integer> list = new ArrayList<Integer>();
    5.       ListNode temp = listNode;
    6.       while(temp != null) {
    7.           list.add(0,temp.val);
    8.           temp = temp.next;
    9.       }
    10.       return list;
    11.   }
    12. }

    2、递归实现

  • 时间复杂度：O（n）

  • 空间复杂度：O（n）
    1. import java.util.ArrayList;
    2. public class Solution {
    3.   ArrayList<Integer> list = new ArrayList<Integer>();
    4.   public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    5.       if(listNode != null) {
    6.           printListFromTailToHead(listNode.next);
    7.           list.add(listNode.val);
    8.       }
    9.       return list;
    10.   }
    11. }