题目描述

输入一个链表，从尾到头打印链表每个节点的值。返回新链表的头结点。

 

 

方法一：用stack，或者最好vector.reverse

vector
      
        printListFromTailToHead(struct ListNode* head)        {            stack
       
         st;            vector
        
          rtn;            while(head)            {                st.push(head->val);                head= head->next;            }            while(!st.empty())            {                int tmp = st.top();                st.pop();                rtn.push_back(tmp);            }                        return rtn;        }
        
       
      

 

方法二：递归在本质上就是一个栈结构，于是很自然地想到用递归来实现。要实现反过来输出链表，每访问到一个结点的时候，先递归输出它后面的结点，再输出该结点自身，这样链表的输出结构就反过来了。

vector
      
        printListFromTailToHead1(struct ListNode* head)        {            vector
       
         rtn;            print(head, rtn);            return rtn;        }        void print(ListNode* head, vector
        
          &rtn)        {            if(head == NULL)                return;            print(head->next, rtn);            rtn.push_back(head->val);        }