从尾到头打印链表

题目描述

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

链表结构

class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}

解题思路一 （头插法）

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;
}

解题思路二

先将所有值插入结果集list，然后首尾向中间两两互换

public static ArrayList<Integer> printListFromTailToHead2(ListNode listNode) {
    ArrayList<Integer> list = new ArrayList<Integer>();
    while (listNode != null){
        list.add(listNode.val);
        listNode = listNode.next;
    }
    int right = list.size() - 1;
    int left = 0;
    while (left < right){
        //两两互换
        int leftValue = list.get(left);
        int rightValue = list.get(right);
        list.set(left, rightValue);
        list.set(right, leftValue);
        left ++;
        right --;
    }
    return list;
}

解题思路三

运用栈后进先出的特点，进行倒序

public ArrayList<Integer> printListFromTailToHead3(ListNode listNode) {
    Stack<Integer> stack = new Stack<Integer>();
    ArrayList<Integer> list = new ArrayList<Integer>();
    while (listNode != null){
        stack.push(listNode.val);
        listNode = listNode.next;
    }
    while (!stack.empty()){
        //栈非空，弹栈
        list.add(stack.pop());
    }
    return list;
}

解题思路四

递归实现倒序

public ArrayList<Integer> printListFromTailToHead4(ListNode listNode) { //递归实现
    ArrayList<Integer> list = new ArrayList<Integer>();
    pushData(listNode, list);//将后面部分的进行倒序插入
    return list;
}
public void pushData(ListNode listNode, ArrayList<Integer> list){
    if(listNode ==null){
        return ;
    }else if(listNode.next == null){
        //最后一个结点
        list.add(listNode.val);
    }else{
        pushData(listNode.next, list);
        list.add(listNode.val);
    }
}