[剑指offer]从尾到头打印链表

穿插一下牛客的《剑指Offer》的题，也算是换换口味吧。感兴趣的童鞋也可以来试试呀：https://www.nowcoder.com/ta/coding-interviews?page=1

题目描述

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

思路：最简单的想法，利用栈的特性就行了。

solution1:

 1 /**
 2 *  struct ListNode {
 3 *        int val;
 4 *        struct ListNode *next;
 5 *        ListNode(int x) :
 6 *              val(x), next(NULL) {
 7 *        }
 8 *  };
 9 */
10 class Solution {
11 public:
12     vector<int> printListFromTailToHead(ListNode* head) {
13       vector<int> vec;
14       ListNode* p = head;
15       stack<int>st;
16       while(p != nullptr)
17       {
18         st.push(p->val);
19         p = p->next;
20       }
21       while(!st.empty())
22       {
23         vec.push_back(st.top());
24         st.pop();
25       }
26       return vec;
27     }
28 };

solution2:

思路：这种题目感觉可以用递归，但是如何书写递归才是难点。

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
       vector<int> vec;
       FromTailToHead(head,vec);
       return vec;
    }
    void FromTailToHead(ListNode* node,vector<int>& vec)
    {
      if(node == nullptr) return;
      FromTailToHead(node->next,vec);
      vec.push_back(node->val);
    }
};