題目描述
輸入一個(gè)鏈表，從尾到頭打印鏈表每個(gè)節(jié)點(diǎn)的值杭棵。
棧實(shí)現(xiàn)
要解決這個(gè)問(wèn)題扣草，肯定要遍歷鏈表，從頭到尾遍歷鏈表颜屠，從尾到頭輸出值，典型的“后進(jìn)先出”鹰祸，自然可以想到用棧來(lái)解決甫窟。
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> vals;
stack<ListNode*> nodes;
ListNode* pNode=head;
while(pNode!=NULL){
nodes.push(pNode);
pNode=pNode->next;
}
while(!nodes.empty()){
pNode=nodes.top();
vals.push_back(pNode->val);
nodes.pop();
}
return vals;
}
};
遞歸實(shí)現(xiàn)
遞歸本質(zhì)上是一個(gè)棧結(jié)構(gòu)，要實(shí)現(xiàn)反過(guò)來(lái)輸出鏈表蛙婴，可以每訪問(wèn)到一個(gè)節(jié)點(diǎn)的時(shí)候粗井，先遞歸輸出它后面的節(jié)點(diǎn)，再輸出節(jié)點(diǎn)本身。
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> vals;
PrintListReversing(head,vals);
return vals;
}
void PrintListReversing(ListNode *pNode, vector<int> &vals){
if(pNode!=NULL){
if(pNode->next!=NULL)
PrintListReversing(pNode->next,vals);
vals.push_back(pNode->val);
}
}
};
