一道打印链表的题我写了几种方法

阿粉相信大家对链表都非常的熟悉，而阿粉最近面试的时候，就遇到了一个一个面试官，在面试的过程中，面试官给阿粉出了一个比较好玩的问题，让阿粉提供多种实现方式来进行实现，得亏阿粉之前看了(背了)好多的面试题，于是阿粉就开始了自己的表演。

什么是链表

百度百科说：

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

一般的链表都是用来和数组进行区分的，与数组不同的是，它是用一组任意的存储单元来存储线性表中的数据，存储单元不一定是连续的，而且链表的长度不是固定的。

而数组则是顺序存储结构，链表通过指针连接元素，而数组则是把所有元素按顺序进行存储，链表插入和删除元素不需要移动元素，数组删除和增加元素需要移动元素。

这也是链表和数组之间的区别。

说完了什么是链表之后，阿粉就来说说这个面试题吧。

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

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

那么这个题目都有哪些的实现思路呢？

当面试官给出这个题目的时候，很多人的第一印象，什么鬼，你想让我怎么实现？

给我一个链表，然后让我倒着来打印，这是不是还得有排序呢？

于是阿粉就开始动手了，第一个思路，阿粉第一个想到的就是Collections.reverse()方法，然后刚准备写，面试官笑着说：你给我住手，别想偷懒！

那我们就先来看看使用Collections.reverse()怎么来实现的

Collections.reverse()

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    ArrayList<Integer> ret = new ArrayList<>();
    while (listNode != null) {
        ret.add(listNode.val);
        listNode = listNode.next;
    }
    Collections.reverse(ret);
    return ret;
}

这实际上就是一个偷懒的写法，在我们处理链表的时候，把链表的数据加入到 List 中，然后调用 Collections.reverse() 的方法对 List 进行一个反转，这样就相当于是反向的把这个链表给输出出来了。

这方法实际上是最简单的方法，但是被面试官笑着阻止了，他也知道我想偷懒。

去掉这种简单的实现方法之后，我们就得再考虑其他的实现方式了，毕竟有这个题目，那肯定就不是只有一种解决方案，只不过是考虑那种解决方案比较合适罢了，在日常的工作中也是这样，选择最适合自己项目的方案才是最合适的。

第二种，那就是使用栈的递归策略

栈的特点就是后进先出，始终使用top和pop语句来实现每一个元素的遍历，同时在使用pop和top函数的时候，要先使用empty来判断栈是否为空，在这里使用栈也是相对来说比较合适的。

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    Stack<Integer> stack = new Stack<>();
    while (listNode != null) {
        stack.add(listNode.val);
        listNode = listNode.next;
    }
    ArrayList<Integer> ret = new ArrayList<>();
    while (!stack.isEmpty()) {
        ret.add(stack.pop());
    }
    return ret;
}

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    ArrayList<Integer> ret = new ArrayList<>();
    if(listNode != null) {
        ret.addAll(printListFromTailToHead(listNode.next));
        ret.add(listNode.val);
    }
    return ret;
}

这时候阿粉绞尽脑汁的想法已经是没有其他的方式来实现了，这时候面试官提问，因为阿粉只能想到这两种方式来实现这个链表倒序打印。

但是面试官对阿粉还是比较柔和的，直接给提示，还有没一种另外一种方法，也能实现链表的倒序呢？这时候面试官，你了解头插和尾插么？于是阿粉灵机一动，发现是呀，还有头插法呀。

头插法和尾插法

头插法：在头结点（为了操作方便，在单链表的第一个结点之前附加一个结点，称为头结点。头结点的数据域可以存储数据标题、表长等信息，也可以不存储任何信息，其指针域存储第一个结点的首地址）之后插入数据，其特点是读入的数据顺序与线性表的逻辑顺序正好相反。

尾插法：将每次插入的新结点放在链表的尾部。

也就是说，可以使用头插法来实现，这样的话，读的顺序正好和逻辑顺序相反，就又出现了一种实现链表倒序打印的方法了呀。既然说，那就得好好实现一下。

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    // 头插法构建逆序链表
    ListNode head = new ListNode(-1);
    while (listNode != null) {
        ListNode memo = listNode.next;
        listNode.next = head.next;
        head.next = listNode;
        listNode = memo;
    }
    // 构建 ArrayList
    ArrayList<Integer> ret = new ArrayList<>();
    head = head.next;
    while (head != null) {
        ret.add(head.val);
        head = head.next;
    }
    return ret;
}

这样的话，就简单实现了使用头插法来进行链表倒序打印。

面试官看到阿粉反应这么快，也就没再多说其他的了，至于收没收到 offer，只是说还有两天以后再进行第二面了，阿粉得好好准备一下面试了，不然下次还不知道会问到什么样子的问题呢。

代码参考：

《剑指Offer》