@TOC

剑指offer 06 从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入： head = [1,3,2]
输出： [2,3,1]

限制：

$0 <= 链表长度 <= 10000$

小提示：在面试中，如果我们打算修改输入的数据，则最好先问面试官是不是允许修改。

解法一：使用递归，不改变原链表

要逆序打印链表 1->2->3（3,2,1)，可以先逆序打印链表 2->3(3,2)，最后再打印第一个节点 1。而链表 2->3 可以看成一个新的链表，要逆序打印该链表可以继续使用求解函数，也就是在求解函数中调用自己，这就是递归思想。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        if(head == null) return new int[]{};
        //得到反向遍历链表后的list，然后赋值给数组arr
        List<Integer> list = getList(head);
        int[]  arr = new int[list.size()];
        for(int i = 0;i < list.size(); i++){
            arr[i] = list.get(i);
        }
        return arr;
    }

    //将链表先存到List中
    public List<Integer> getList(ListNode head){
        List<Integer> list = new ArrayList<>();
        if(head.next != null){
            list.addAll(getList(head.next));
        }
        list.add(head.val);
        return list;
    }
}

上面基于递归的代码看起来很简洁，但有一个问题，当链表非常长的时候，就会导致函数调用的层级很深，从而可能导致函数调用栈的溢出。故不可取，只是说这个思路在其他题中或许会用到，比如有些不得不用递归的题。

解法二：使用栈，不改变原链表

事实上，看到反向，逆序等词语的时候，我们第一反应就应该是栈的先进后出特性，故在空间复杂度允许的情况下是完全可以考虑先使用栈的。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        if(head == null) return new int[]{};
        Stack<Integer> stack = new Stack<>();
        ListNode cur = head;//为了避免使用head = head.next而改变原链表，声明cur来辅助遍历
        while(cur != null){
            stack.push(cur.val);
            cur = cur.next;
        }

        int[] arr = new int[stack.size()];
        //注意这里用的是arr.length;而不是stack.size();因为stack一直在pop,长度在改变
        for(int i = 0;i < arr.length; i++){
            arr[i] = stack.pop();
        }
        return arr;
    }
}

解法三：头插法将链表反转，修改原链表，空间复杂度为$O(1)$

头插法: 共三个关键结点，如图：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        if(head == null) return new int[]{};
        //由于用的是头插法，即后面的节点需要插在当前头节点之前，所以声明一个虚拟头节点
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy.next.next;//表示本次要插入到dummy后的结点，即插入到原始链表的头节点位置
        ListNode tail = head;//tail指向一直不变，改变的是tail.next,用于将已经反转的部分链表和剩余还需要反转的链表相连
        int count = 1;//记录节点个数,由于是从第二个节点头插，所以节点个数初始值为1
        while(cur != null){
            ListNode nxt = cur.next;//记住下一个需要头插的节点，避免等下cur.next改变指向，就找不到原来的cur.next了
            cur.next = dummy.next;
            dummy.next = cur;
            tail.next = nxt;//将已经反转的部分链表和剩余还需要反转的链表相连
            cur = nxt;//下一个要头插的节点
            count++;
        }

       int[] arr = new int[count];
        ListNode cur2 = dummy.next;
        int i = 0;
        while(cur2 != null){
            arr[i++] = cur2.val;
            cur2 = cur2.next;
        }
        return arr;
    }
}

在要修改原链表，如反转，两两反转，k个一组等反转时，建议画个图，想清楚链表指向的改变过程之后再写代码。