本文共 2678 字，大约阅读时间需要 8 分钟。

题目描述

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

示例 1：

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

输出：[2,3,1]

限制：

0 <= 链表长度 <= 10000

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

C++

方法1：用栈 T(n)=O（n）,S(n)=O（n）

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {
   public:    vector
   
     reversePrint(ListNode* head) {
           //方法一：用栈，循环遍历入栈，循环遍历出栈        stack
    
       s;               vector
     
       res;        if(!head)            return res;         ListNode* cur;         cur=head;        while(cur){
               s.push(cur);            cur=cur->next;        }        while(!s.empty()){
     //这里我起初用的while(s.top())就一直有错            res.push_back(s.top()->val);            s.pop();        }        return res;    }};
     
    
   

Line 170: Char 16: runtime error: reference binding to misaligned address 0xbebebebebebec0b6 for type 'ListNode *', which requires 8 byte alignment (stl_deque.h)0xbebebebebebec0b6: note: pointer points here
   
    SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_deque.h:180:16
   

关于上边我用s.top()出错的问题，我觉得得堆栈为空了，stk.top()就变成nullptr了呗。事实并非如此，堆栈为空时top元素并不是空，而是-1，因此堆栈为空时不能调用top()函数，同时也不能调用pop()函数。

方法二：反正需要遍历两次，不用栈遍历两次也能实现

遍历一次栈，计数，再将数组逆序赋值就好 O(n)=n; S（n）=n;

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {
   public:    vector
   
     reversePrint(ListNode* head) {
            vector
    
      res;        if(!head)  return  res;        ListNode* cur=head;        int count=0;        while(cur){
               count++;            cur=cur->next;        }       res.resize(count);        cur=head;        for(int i=count-1;i>=0;i--){
                   res[i]=cur->val;                cur=cur->next;        }        return res;    }};
    
   

方法三：递归

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {
   public:       vector
   
     reversePrint(ListNode* head) {
           vector
    
      res;         if(!head) return res;         recur(res,head);            return res;    }    void recur(vector
     
       & res,ListNode * head){
               //递归停止条件                     if(!head)  return ;            //本级递归干什么            recur(res,head->next);            res.push_back(head->val);    }};
     
    
   

当链表非常长的时，会造成递归调用很深，有可能导致函数调用栈溢出，所以鲁棒性不好。