Reverse output list

1 idea: first, traverse the linked list, and use an array to store the value of the linked list. Then reverse the array and return the array.
2 core modules
① traversal list
My mistake: head is a virtual head node and does not store meaningful linked list data.
The first data of the linked list is stored in the head.
Traverse linked list: defines a pointer p to ListNode type to point to the head node. Only when p is not empty, the data field of P is stored in the array, and P is pointed to the next node. Finally, the array is returned. Corresponding code:

ListNode * p=head;
 while(p!=NULL) 
        {
            Ldata.push_back(p->val);
            p=p->next;
            
        }

Extreme case description: if the incoming linked list is empty, no operation will be performed and the array will be returned directly. The output is empty because the array is declared only.

② reverse array
There are three ways to reverse an array:
Method 1: custom implementation of inversion, pay attention not to inversion on the array itself, it will be wrong to overwrite, and then define a new array, and store the result of inversion into the new array.

for(int i=0;i<Ldata.size();i++)
   res.push_back(Ldata[Ldata.size()-1-i]);
  return res;

Mode 2: use the reverse() function in algorithm, and pay attention to the parameters passed in by the reverse function

reverse(Ldata.begin(),Ldata.end());
 return Ldata;

Mode 3: use the reverse iterator in vector

vector <int> ::reverse_iterator rit=Ldata.rbegin();
 for(;rit!=Ldata.rend();rit++)
       res.push_back(*rit);
 return res;

3 complete code

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector <int> Ldata,res;
        
        ListNode * p=head;
       
        while(p!=NULL) //There is a problem with the understanding of the head pointer. The head pointer can also store the effective data of the linked list
        {
            Ldata.push_back(p->val);
            p=p->next;
            
        }
        
        //Method 1: when you define your own inversion, do not reverse the array itself, which will lead to errors
        //for(int i=0;i<Ldata.size();i++)
          // res.push_back(Ldata[Ldata.size()-1-i]);
        // return res;
        //Method 2: use the reverse() function in algorithm
       //reverse(Ldata.begin(),Ldata.end());
         // return Ldata;
         //Method 3: use the reverse iterator in vector
        vector <int> ::reverse_iterator rit=Ldata.rbegin();
        for(;rit!=Ldata.rend();rit++)
            res.push_back(*rit);
         return res;
    }
};

4 harvest:
If there is only a part of pass rate of online programming problems, it is not necessarily that the boundary situation is not considered, but also that there may be logical errors.

Keywords: Programming

Added by laurus on Mon, 18 Nov 2019 20:27:35 +0200