数据结构入门教程-单链表经典面试题分析(2)

前面的一篇文章我们为了加深对链表的学习，通过一道经典的面试题单链表反转的问题进行实际代码的操作，相信大家都链表都有了好感发现其实也挺有意思的，这篇我们同样通过一道面试题来对我们的链表更上一层的学习，直接入正题.

题目

• 实现从尾到头打印单链表

想必大家心里都有了想法，究竟怎么样的想法，先保留，看看我的思路在进行从优比较，首先来看张图：

单链表图.png

上图就是我的单链表,在结合题目的意思，无法就是对该链表进行逆序打印，既然是逆序打印的话，我可不可用上节的单链表反转呢？不猜了，我来分析下：

• 第一种方式:我们可以对该链表进行反转操作，然后遍历好像就可以完成了哈,但是不知有没有想过，我们在反转链表时，已经破坏了链表的结构，所以这种操作不建议.
• 方式二：我们可以借助于另外一个数据结构栈(Stack)的先进后出特性来实现对该链表的逆序打印操作.

通过简单的两种方式对比，想必大家知道怎么做了，不过关于栈数据结构这里不知道不影响我们操作，关于它的详解我们后面来说，确定了实现的思路，接下来我们用代码来实现。

代码实现

//面试题：逆序打印单链表(利用栈的特性来完成 现金后出) 不改变链表原来的结构
public static void resversePrint(HeroNode head){
    if (head.next == null){
        return; //表明是空链表，直接返回即可
    }
    //1.创建一个栈，将各个节点压入栈中
    Stack<HeroNode> stack = new Stack<>();
    //创建一个辅助指针
    HeroNode cur = head.next; //指向链表的第一个节点
    //2循环链表进行压入stack
    while (cur !=null){
        stack.push(cur); //将当前元素压入stack
        cur = cur.next; //后移动一位接着遍历
    }
    //3.将stack节点进行打印
    while (stack.size() > 0){
      //方法stack.pop()出栈的操作
        System.out.println(stack.pop());
    }
}

代码分为了3步实现，有详细的注释，这里就不多说了，我们来测试一把，代码如下：

public class SingleLinkListCase {

    public static void main(String[] args) {
    //创建节点
    HeroNode node1 = new HeroNode(1,"宋江","及时雨");
    HeroNode node2 = new HeroNode(2,"卢俊义","玉麒麟");
    HeroNode node3 = new HeroNode(3,"吴用","智多星");
    HeroNode node4 = new HeroNode(4,"林冲","豹子头");
    //创建链表，并添加
    SingleLinkList singleLinkList = new SingleLinkList();
    singleLinkList.addOrderByNo(node1);
    singleLinkList.addOrderByNo(node4);
    singleLinkList.addOrderByNo(node2);
    singleLinkList.addOrderByNo(node3);
    //显示链表
    singleLinkList.show();
    System.out.println("逆序打印链表测试=============");
    resversePrint(singleLinkList.getHead());

结果如图所示：

逆序打印链表结果图.png

从结果图可以看出，我们实现了单链表的逆序打印,亲测有效，不信你试试喽~