从尾到头打印链表

问题

牛客上面有这样一个题，输入如下链表

public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}
// 完成下面方法
ArrayList<Integer> printListFromTailToHead(ListNode listNode){}

然后让你从尾到头输出一个ArrayList

题解

遍历元素添加到list的第一位
使用ArrayList的 add(int index, E element)方法，遍历一遍node 放进去
这样过后 arraylist就是一个反链表。
这个方法 看是简单，可是效率确实异常底下，原因在这个add方法里面，
添加到第一位，会将第一位之后的所有数据往后移动一位。

我思考了下，可以使用 首位置换法 也是受到二分查找方法的启发，想出来的方法。
思想就是：将第一位和最后一位交换位置，然后第二位和倒数第二位，以此类推就能将整个链表反转。

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    if(listNode == null){
        return new ArrayList<>();
    }
    ArrayList<Integer> arrayList = new ArrayList<>();
    arrayList.add(listNode.val);
    while (listNode.next != null) {
        listNode = listNode.next;
        arrayList.add(listNode.val);
    }

    int l = 0, r = arrayList.size() - 1, m = (r + l) / 2;
    while (l <= m) {
        int a = arrayList.get(l);
        arrayList.set(l, arrayList.get(r));
        arrayList.set(r, a);
        l++;
        r--;
    }

    return arrayList;
}