剑指offer第二版-6.从尾到头打印链表

描述：输入一个链表的头节点，从尾到头打印每个节点的值。

思路：从尾到头打印，即为“先进后出”，则可以使用栈来处理；考虑递归的本质也是一个栈结构，可递归输出。

考点：对链表、栈、递归的理解。

package com.java.offer;

import java.util.Stack;

/**

 * @since 2019年2月14日 下午2:13:20

 * @author xuchao

 *

 */

public class P6_PrintListInReversedOrder {

    public static class ListNode<T> {

        public T val;

        public ListNode<T> next;

        public ListNode(T val) {

            this.val = val;

            this.next = null;

        }

    }

    // 方法1：(非递归)使用Stack栈的先push后pop

    public static <T> void printListReverse(ListNode<T> listNode) {

        Stack<ListNode<T>> stack = new Stack<>();

        while(listNode!=null) {

            stack.push(listNode);

            listNode = listNode.next;

        }

        while (!stack.isEmpty()) {

            System.out.println(stack.pop().val);

        }

    }

    // 方法2：递归

    public static <T> void printListReverse_rec(ListNode<T> listNode) {

        if (listNode != null) {

            if (listNode.next != null) {

                printListReverse_rec(listNode.next);

            }

            System.out.println(listNode.val);

        }

    }

    public static void main(String[] args) {

        ListNode<Integer> head = new ListNode<Integer>(1);

        head.next = new ListNode<Integer>(2);

        head.next.next = new ListNode<Integer>(3);

        printListReverse_rec(head);

        printListReverse(head);

    }

}