逆序打印单链表（四种解法）

题目描述

输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

链表的结构

  struct ListNode {
        int val;
       struct ListNode *next;
       ListNode(int x) :
           val(x), next(NULL) {
       }
 };

1.利用栈的特性

class Solution {
public:    
    vector<int> printListFromTailToHead(ListNode* head) 
    {
        
        stack<int> s ;
        vector<int> v;
         if(nullptr == head)
            return v;
       
        ListNode* cur = head;
        while(cur)
        {
            s.push(cur->val);
            cur = cur -> next;
        }
        while(!s.empty())
        {
            v.push_back(s.top());
            s.pop();
        }
        return v;
    }
};

2.利用递归

class Solution {
public:   
    vector<int> printListFromTailToHead(ListNode* head) 
    {
        vector<int> v;
         if(nullptr == head)
            return v; 
          v = printListFromTailToHead(head->next);
          v.push_back(head->val); 
        return v;  
    }
};

3.利用数组

class Solution {
public:     
    vector<int> printListFromTailToHead(ListNode* head) 
    {        
        vector<int> v;
        if(head == nullptr)
            return v;  
        ListNode* cur = head;
        while(cur)
        {
            v.push_back(cur->val);
            cur = cur->next;
        }
       // reverse(v.begin(),v.end()); //也可以用STL直接提供的反转函数
       int temp=0;      
       int i=0,j=value.size()-1;    
        while(i<j)
        {         
           temp=value[i];    //也可以用swap函数，swap(value[i],value[j]); 
           value[i]=value[j];        
            value[j]=temp;        
                i++;          
                j--;   
           }      
        return value;
    }
};

4.利用反向迭代器

class Solution {
public:
      
    vector<int> printListFromTailToHead(ListNode* head) 
    {
       
        vector<int> v;
        if(head == nullptr)
            return v;  
        ListNode* cur = head;
        while(cur)
        {
            v.push_back(cur->val);
            cur = cur->next;
        }
         return vector<int>(v.rbegin(), v.rend());
    }
};

<stron>：逆序打印单链表</stron>