从头打印一个链表

题目描述:

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

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        
    }
}

思路

第一种思路

从头到尾递归输出，递归是属于栈的一种思想，其实就是倒序往ArrayList里面进行压入；
如果我们想实现正序，只需要把压入ArrayList的操作在递归函数之前就可以了。

第二种思路

任何一种递归都能用循环写出来，所以第二种方法就是使用循环实现。

代码实现

第一种思路

import java.util.ArrayList;
public class Main {
   static ArrayList<Integer> arrayList = new ArrayList<>();
    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        ListNode listNode11 = new ListNode(2);
        ListNode listNode12 = new ListNode(3);
        listNode.next = listNode11;
        listNode11.next = listNode12;
        arrayList = printListFromTailToHead(listNode);
    }
    public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode != null)
        {
            printListFromTailToHead(listNode.next);
            arrayList.add(listNode.val);//上下两行交换顺序就可以实现正序
        }
        return arrayList;
    }
}
class ListNode
{
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}

第二种思路

每次插入list的时候都在头上插入，这种方式java实现是通过向后移插入后面的元素，所以每次这样效率会很低。

public  ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
       ArrayList<Integer> arrayList = new ArrayList<>();
       while (listNode!=null)
       {
           arrayList.add(0,listNode.val);//这种方式java实现是通过向后移插入后面的元素，所以每次这样效率会很低。
           listNode = listNode.next;
       }
       return arrayList;
   }

顺序插入完后，进行反转。

public  ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
       ArrayList<Integer> arrayList = new ArrayList<>();
       while (listNode!=null)
       {
           listNode = listNode.next;
       }
       Collections.reverse(arrayList);//使用Collections的reverse方法，直接将list反转,这样只操作一次，不需要再每次去后移，相对而言效率好一点。
       return arrayList;
   }