剑指offer面试题[5]-从尾到头打印链表

迈不过友情╰ 2022-06-13 01:24 139阅读 0赞

## 目描述 ##

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

/\*\*

\*  struct ListNode \{  
\*        int val;  
\*        struct ListNode \*next;  
\*        ListNode(int x) :  
\*              val(x), next(NULL) \{  
\*        \}  
\*  \};  
\*/  
  
方法一：  
//用栈来实现  
/\*class Solution \{  
public:  
    vector<int> printListFromTailToHead(ListNode\* head) \{  
        std::stack<ListNode\*> nodes;   //用栈来实现，因为栈是"后进先出".  
        ListNode\* pNode=head;  
        vector<int> vec;  
        while(pNode!=NULL)  
          \{  
            nodes.push(pNode);  
            pNode=pNode->next;  
          \}  
        while(!nodes.empty())  
          \{   
            pNode=nodes.top();    //返回栈顶的元素，但不删除该元素  
            //vec\[i\]=pNode->val;           容器不能这样赋值  
            vec.push\_back(pNode->val);  
            nodes.pop();          //删除栈顶元素，但不返回其值  
          \}    
        return vec;  
    \}  
\};\*/  
  
方法2：  
//利用递归来实现       递归在本质上就是一个栈结构，于是很自然地想到了用递归实现  
class Solution \{    //要实现反过来输出链表，我们每访问到一个结点的时候，先递归输出它后面的结点，再输出该结点本身，这样链表的输出结果就反过来了  
public:  
    vector<int> printListFromTailToHead(ListNode\* head) \{  
        vector<int> vec;  
        if(head!=NULL)  
          \{  
             if(head->next!=NULL)  
                 \{  
                    vec=printListFromTailToHead(head->next);  // 这里一定要用vec=，不然递归时没有上一层的值，最终vec只会输出一个值  
                 \}  
             vec.push\_back(head->val);  
          \}  
     return vec;  
    \}  
\};