剑指offer（3）之从尾到头打印链表

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

方法一：非递归

　　　　思路1：先用while循环遍历链表的每一个节点，并把每个节点的值存进ArrayList里，之后反向遍历ArrayList，把值存进另外一个ArrayList里，然后返回

　　　　代码如下：

import java.util.ArrayList;

class ListNode
{

    int val;
    ListNode next;
    ListNode(int x)
    {
        val = x;
    }
}

public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list=new ArrayList<Integer>();
        ArrayList<Integer> list2=new ArrayList<Integer>();
         
        while (listNode!=null)
        {
            list.add(listNode.val);
            listNode=listNode.next;
        } 
        for (int i = list.size()-1; i >= 0; i--)
        {
            list2.add(list.get(i));
        }
         
        return list2;
 
    }
}

　　　　思路2：还是遍历的思路，只是直接使用ArrayList的一个方法list.add(0,listNode.val)，每次从头插入，生成反向链表

　　　　代码如下：

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list=new ArrayList<Integer>();
         
         
        while (listNode!=null)
        {
            list.add(0,listNode.val);
            listNode=listNode.next;
        } 
         
        return list;
 
    }
}

方法二：递归

　　　　思路：每次在方法中使用子节点递归调用方法在ArrayList的add操作之前，这样当递归调用结束后会先运行最后一个节点的add方法，依次add，生成反向ArrayList返回

　　　　代码如下：

import java.util.ArrayList;
public class Solution {
    ArrayList<Integer> list=new ArrayList<Integer>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
         
        if (listNode != null)
        {
            printListFromTailToHead(listNode.next);
            list.add(listNode.val);
        }
        return list;
 
    }
}