剑指Offer面试题：3.从尾到头打印链表

一、题目
输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
二、思路
1.使用头插法
使用头插法可以得到一个逆序的链表。
头结点和第一个节点的区别：
头结点是在头插法中使用的一个额外节点，这个节点不存储值；
第一个节点就是链表的第一个真正存储值的节点。

2.递归
要逆序打印链表 1->2->3（3,2,1)，可以先逆序打印链表 2->3(3,2)，最后再打印第一个节点 1。而链表 2->3 可以看成一个新的链表，要逆序打印该链表可以继续使用求解函数，也就是在求解函数中调用自己，这就是递归函数。
3.使用栈
栈具有后进先出的特点，在遍历链表时将值按顺序放入栈中，最后出栈的顺序即为逆序。
————————————————
三、解决问题

package swordoffer;
/**
 * @author LQ
 * @version 1.0
 * @date 2020\3\11 0011 10:15
 */
//输入一个链表的头结点，从尾到头反过来打印出每个结点的值。结点定义如下：
public class ListNode {
    int val;
    ListNode next = null;

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

package swordoffer;

/**
 * @author LQ
 * @version 1.0
 * @date 2020\3\11 0011 9:22
 */

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

/**
 *
 * 题目描述
   输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
 */
public class Solution03 {
    public static void main(String[] args) {
        System.out.println("==============================");
        Solution03 sword = new Solution03();
        sword.test1();
        System.out.println("==============================");
        sword.test2();
        System.out.println("==============================");
        sword.test3();
        System.out.println("==============================");
    }

    /**
     * 第一种方法：使用递归
     要逆序打印链表 1->2->3（3,2,1)，可以先逆序打印链表 2->3(3,2)，
     最后再打印第一个节点 1。而链表 2->3 可以看成一个新的链表，
     要逆序打印该链表可以继续使用求解函数，
     也就是在求解函数中调用自己，这就是递归函数。
     * @param listNode
     * @return
     */
    public ArrayList<Integer> printListFromTailToHead01(ListNode listNode) {
        //alt+shit+L 提示补全
        ArrayList<Integer> ret = new ArrayList<>();
        if(null != listNode){
            //boolean addAll(Collection<? extends E> c)
            //按照指定 collection 的迭代器所返回的元素顺序
            //将该 collection 中的所有元素添加到此列表的尾部
            //addAll是传入一个List，将此List中的所有元素加入到当前List中
            //也就是当前List会增加的元素个数为传入的List的大小
            ret.addAll(printListFromTailToHead01(listNode.next));
            //add是将传入的参数作为当前List中的一个Item存储，即使你传入一个List也只会另当前的List增加1个元素
            ret.add(listNode.val);
        }
        return ret;
    }

    /**
     * 第二种方法：使用头插法---一般喜欢考察此方法的理解
     使用头插法可以得到一个逆序的链表。
     头结点和第一个节点的区别：
     头结点是在头插法中使用的一个额外节点，这个节点不存储值；
     第一个节点就是链表的第一个真正存储值的节点。
     * @param listNode
     * @return
     */
    public ArrayList<Integer> printListFromTailToHead02(ListNode listNode) {
        //1.头结点是在头插法中使用的一个额外节点，这个节点不存储值；
        ListNode head = new ListNode(-1);
        //2.将结点操作为: -1 => 3 => 2 => 1
        while(null != listNode){
            ListNode memo = listNode.next;//2.1 缓存下一个结点位置
            listNode.next = head.next;//2.2 断开
            head.next = listNode;//2.3 -1 => 1
            listNode = memo;//2.4 将listNode指向下一个结点位置
        }
        //3.将结点操作为:  1 => 2 => 3 按照顺序添加到ArrayList中
        ArrayList<Integer> ret = new ArrayList<>();
        head = head.next;
        while(null != head){
            ret.add(head.val);
            head = head.next;
        }
        return ret;
    }
    /**
     * 第三种方法：使用栈
       栈具有后进先出的特点
       在遍历链表时将值按顺序放入栈中，最后出栈的顺序即为逆序。
     */
    public ArrayList<Integer> printListFromTailToHead03(ListNode listNode) {
        Stack<Integer> stack = new Stack<>();
        //1.在遍历链表时将值按顺序放入栈中
        while(null != listNode){
            stack.add(listNode.val);
            listNode = listNode.next;
        }
        //2.最后出栈的顺序即为逆序。
        ArrayList<Integer> ret = new ArrayList<>();
        while(!stack.isEmpty()){
            ret.add(stack.pop());
        }
        return ret;
    }
    /**
     * 测试用例：
     * 1.多个结点链表
     */
    public void test1() {
        ListNode ListNode1 = new ListNode(1);
        ListNode ListNode2 = new ListNode(2);
        ListNode ListNode3 = new ListNode(3);
        ListNode1.next=ListNode2;
        ListNode2.next=ListNode3;
        System.out.println("采用递归：");
        System.out.println(printListFromTailToHead01(ListNode1));
    }
    public void test2() {
        ListNode ListNode1 = new ListNode(1);
        ListNode ListNode2 = new ListNode(2);
        ListNode ListNode3 = new ListNode(3);
        ListNode1.next=ListNode2;
        ListNode2.next=ListNode3;
        System.out.println("采用头插法：");
        System.out.println(printListFromTailToHead02(ListNode1));
    }
    public void test3() {
        ListNode ListNode1 = new ListNode(1);
        ListNode ListNode2 = new ListNode(2);
        ListNode ListNode3 = new ListNode(3);
        ListNode1.next=ListNode2;
        ListNode2.next=ListNode3;
        System.out.println("采用栈：");
        System.out.println(printListFromTailToHead03(ListNode1));
    }
}

努力也是需要学习的，别再让你的努力，只感动了自己！愿你的每一次努力，都能为自己和别人创造价值。