【剑指offer】6.从头到尾打印链表

6.从尾到头打印链表

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

示例 1：

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

1.使用栈

th:逆序打印 我们可以将链表loop一遍，push到栈中。然后pop出 因为栈是先进后出 所有最后顺序就是逆序的顺序。 这里建议push最好是val push node的话 占用的内存空间比较大。

time: O(n) 需要遍历一遍链表

space:O(n) 需要大小为size的数组存储数据。

public int[] reversePrint(ListNode head) {
        if(head == null){
            return new int[0];
        }
        Stack<ListNode>stack = new Stack<>();
        
        ListNode cur = head;
        while(cur!=null){
            stack.push(cur);
            cur = cur.next; 
        }
        int [] array = new int [stack.size()];
        int i = 0;
        while(!stack.isEmpty()){
            array[i++] = stack.pop().val;
        }
        return array;
    }

2.递归法

th: 递推阶段:每次传入head.next 以head.next ==null 为终止条件，此时返回。

回溯节点:层层回溯时，将以当前节点值加入列表。

最后转换成int数组即可。

time:O(n) 遍历链表n次

space:O(n) 系统递归需要使用O(n)的栈空间

  List<ListNode> list = new ArrayList<>();
    
        /***
          2.递归
        */
        public int[] reversePrint(ListNode head) {
          //递归
          reverse(head);
          int [] array = new int [list.size()];
        
          for(int i=0;i<list.size();i++){
              array[i] = list.get(i).val;
          }
          return array;
        }
    
        public void reverse(ListNode curr){
            //1.终止条件
            if(curr == null){
                return;
            }
          	//2.递归子问题
            reverse(curr.next);
            // 3.业务逻辑
            list.add(curr);
        }

3.头插法

头插法顾名思义是将节点插入到头部，在遍历原始链表时，将当前节点插入新链表的头部，使其称为第一个节点，

链表的操作需要维护后继关系，例如在某个节点node1之后插入一个节点node2,我们可以通过修改后继关系来实现。

node3 = node1.next;
node2.next = node3;
node1.next = node2;

为了能将一个节点插入头部，我们引入了一个叫头结点的辅助节点，该节点不存储值，只是为了方便进行插入操作。不要将头结点与第一个节点混起来，第一个节点是链表中第一个真正存储值的节点。

 //头插法
    public int[] reversePrint(ListNode head) {
        ListNode node = new ListNode(-1);
        int size = 0;
        //1 while   -1 	-->1 
        //2 while   -1 	-->2   -->1
        //3 while   -1 	-->3   -->2  -->1
        while(head != null){
            ListNode memo = head.next;  //存储后继节点
            head.next = node.next;  //
            node.next = head;  //和头结点连接上
            head = memo;  //head 继续遍历下去
            size++; 
        }

        int [] arr = new int [size];
        head = node.next;
        int i = 0;
        while(head != null){
            arr[i++] = head.val;
            head = head.next;
        }
        return arr;
    }