剑指offer06：从尾到头打印链表

题目描述：

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

示例 1：

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

解题思路：

从尾到头打印链表，优先考虑栈，因为想到栈是先进后出的。如果先反转链表再打印的话会破坏链表原来的结构，不建议。

• 创建一个栈，用于存储链表的节点Stack<ListNode>；
• 创建一个指针，初始时指向链表的头节点。

当指针指向的元素非空时，重复下列操作：

• 将指针指向的节点压入栈内
• 将指针移到当前节点的下一个节点

获得栈的大小 size，创建一个数组 print，其大小为 size

• 创建下标并初始化 index = 0
• 重复 size 次下列操作：
• 从栈内弹出一个节点，将该节点的值存到 print[index]
• 将 index 的值加 1
• 返回 print

java代码：

  

   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

       * Definition for singly-linked list.
     
    
   

    

     

    
    

     

       * public class ListNode {
     
    
   

    

     

    
    

     

       * int val;
     
    
   

    

     

    
    

     

       * ListNode next;
     
    
   

    

     

    
    

     

       * ListNode(int x) { val = x; }
     
    
   

    

     

    
    

     

       * }
     
    
   

    

     

    
    

     

       */
     
    
   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     
    public int[] reversePrint(ListNode head) {
     
    
   

    

     

    
    

     
         
     
    
   

    

     

    
    

     
        
     
    
   

    

     

    
    

     
                 
     
    
   

    

     

    
    

     

              Stack<ListNode> stack=new Stack<>();
     
    
   

    

     

    
    

     

              ListNode cur=head;
     
    
   

    

     

    
    

     
        while(cur!=null){
     
    
   

    

     

    
    

     

                  stack.push(cur);
     
    
   

    

     

    
    

     

                  cur=cur.next;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        int size=stack.size();
     
    
   

    

     

    
    

     
        int[] array=new int[size];
     
    
   

    

     

    
    

     
        for(int i=0;i<size;i++){
     
    
   

    

     

    
    

     

                  array[i]=stack.pop().val;
     
    
   

    

     

    
    

     
            
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        return array;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：小小谢先生，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/xiewenrui1996/article/details/112972818