面试题6：从尾到头打印链表

题目：

输入一个链表的头结点，从尾到头反过来打印出每个结点的值。

分析：

比较容易想到的方法是链表的逆置，再遍历输出。此时，对于链表的结构能否改变，取决于面试官的要求，如果面试官允许修改，那么可以采用链表逆置再输出的方式解决。这里假设不能修改链表的结构。

遍历顺序和输出顺序是反向的，可以利用栈这个数据结构，进而可以联想到递归，不过递归有栈深度限制，递归太深就栈溢出了。

解法：

package com.wsy;

import java.util.Stack;

class Node {
    private int value;
    private Node next;

    public Node() {
    }

    public Node(int value, Node next) {
        this.value = value;
        this.next = next;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

public class Main {
    public static void main(String[] args) {
        Node head = init();
        forwardPrint(head);
        reversePrintWithStack(head);
        reversePrintWithRecursive(head);
        reversePrintWithInversion(head);
    }

    public static Node init() {
        Node head = new Node(10, null);
        Node tail = head;
        for (int i = 0; i < 10; i++) {
            Node node = new Node(i, null);
            tail.setNext(node);
            tail = node;
        }
        return head.getNext();
    }

    public static void forwardPrint(Node head) {
        Node node = head;
        while (node != null) {
            System.out.print(node.getValue() + "->");
            node = node.getNext();
        }
        System.out.println();
    }

    public static void reversePrintWithStack(Node head) {
        Stack<Node> stack = new Stack<Node>();
        Node node = head;
        while (node != null) {
            stack.push(node);
            node = node.getNext();
        }
        while (!stack.empty()) {
            node = stack.pop();
            System.out.print(node.getValue() + "->");
        }
        System.out.println();
    }

    public static void reversePrintWithRecursive(Node head) {
        if (head != null) {
            if (head.getNext() != null) {
                reversePrintWithRecursive(head.getNext());
            }
            System.out.print(head.getValue() + "->");
        }
    }

    public static void reversePrintWithInversion(Node head) {
        Node previous = null;
        Node current = head;
        while (current != null) {
            Node temp = current;
            current = current.getNext();
            temp.setNext(previous);
            previous = temp;
        }
        System.out.println();
        forwardPrint(previous);
    }
}