从尾到头打印链表

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

/** 链表节点
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*/

分析题目

链表一种基础的数据结构,从尾到头就是反向遍历链表,通过链表头依次可访问到后继节点，即可得到链表的顺序结构的值。把结果依次存入栈中，再弹出即可得到反向链表值。

解决办法

• Java 代码

import java.util.ArrayList;
import java.util.Stack;

public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        if(listNode == null){
            return arrayList;
       }
        Stack<Integer> stack = new Stack<>();
        while (listNode.next != null){
            stack.push(listNode.val);
            listNode = listNode.next;
        }
        stack.push(listNode.val);
        while (!stack.isEmpty()){
           arrayList.add(stack.pop());
        }
        return arrayList;
    }
}

• JavaScript 代码

JS下面代码array2的作用，也可以采用 unshift 方法代替。多用一个数组变量，空间复杂度高一点。但是比采用unshift函数时间复杂度略低。

function printListFromTailToHead(head)
{    
    let list = head
    if(list == null){
        return [];
    }
    let array1 = []
    let array2 = []
    while(list.next != null){
        array1.push(list.val)
        list = list.next
    }
    array1.push(list.val)
    while(array1.length != 0){
        array2.push(array1.pop())
    }
    return array2
}