剑指Offer——从尾到头打印链表

1、题目描述

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

2、代码实现

package com.baozi.offer;

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

/**
 * @author BaoZi
 * @create 2019-07-10-18:13
 */
public class Offer3 {
    public static void main(String[] args) {
        Offer3 offer3 = new Offer3();
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(3);
        ListNode l4 = new ListNode(4);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = null;
        ArrayList<Integer> reslut = offer3.printListFromTailToHead(l1);
        System.out.println(reslut.toString());
    }

    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        //1、创建一个目标变量，保存元素顺序和原链表的元素顺序刚好相反
        ArrayList<Integer> list = new ArrayList<>();
        //2、先判断给定的原链表是否为空，如果为空则直接返回一个空的目标链表
        if (listNode == null) {
            return list;
        }
        //3、根据题目要求，我们要把链表顺序从尾到头打印输出，所以设置一个栈的数据结构
        Stack<Integer> stack = new Stack<>();
        ListNode temp = listNode;
        //4、通过while循环的方式先把原链表中的元素全部存入栈中
        while (temp != null) {
            stack.push(temp.val);
            temp = temp.next;
        }
        //5、在通过while循环的方式把栈的元素逐一存入目标链表中
        while (!stack.isEmpty()) {
            list.add(stack.pop());
        }
        //6、此时的list链表的元素顺序和原链表的顺序就刚好相反了
        return list;
    }
}

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}