链表面试题--两种方法逆序打印单链表（栈和递归）

方法一： 我们可以遍历链表，可是遍历链表的顺序是从头到尾，而打印（输出）链表的顺序是从尾到头。即第一个遍历到的结点最后一个输出，最后一个遍历到的结点第一个输出。这正号符合栈“先进后出”的思想，所以我们可以用栈来实现。每经过一个结点的时候，把结点放到栈中，当遍历完整个链表后，从栈顶开始逐个输出结点的值，这样就可以逆序打印出该链表了。 具体实现如下：

void List::ReversePrint2(ListNode* phead) { stack<ListNode*> s; if (NULL == phead) { return ; } else { ListNode* pCur = phead; while (pCur != NULL) { s.push(pCur); pCur = pCur->_next; } while (!s.empty()) { pCur = s.top(); cout << pCur->_value << "->"; s.pop(); } } }

方法二： 利用递归来实现，每访问到一个结点的时候，先递归输出它后面的结点，在输出该结点自身，这样也可以逆序打印出该链表。 具体实现：

void List::ReversePrint1(ListNode* phead) { if (phead!=NULL) { if (phead->_next != NULL) { ReversePrint1(phead->_next); } cout << phead->_value << "->"; } }

完整代码如下： List.h

#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<stdio.h> #include<stdlib.h> using namespace std; struct ListNode { ListNode(int value) :_value(value) , _next(NULL) {} int _value; ListNode* _next; }; class List { public: List() :phead(NULL) {} void InitNode(ListNode** phead); //尾插 void PushBack(ListNode** phead,int value); //创建新结点 ListNode* NewNode(int value); //打印链表 void Print(); //从尾到头打印链表(递归) void ReversePrint1(ListNode* phead); //从尾到头打印链表(栈) void ReversePrint2(ListNode* phead); private: ListNode* phead; };

List.cpp

#include"List.h" #include<stack> void List:: InitNode(ListNode** phead) { if (NULL != *phead) *phead = NULL; } void List:: PushBack(ListNode** phead,int value) { if (NULL == *phead) { *phead = NewNode(value); } else { ListNode* pCur = *phead; while (pCur->_next != NULL) pCur = pCur->_next; pCur->_next = NewNode(value); } } ListNode* List:: NewNode(int value) { return new ListNode(value); } void List:: Print() { ListNode* pCur = phead; while (pCur!= NULL) { cout << pCur->_value<<"->"; pCur = pCur->_next; } } void List::ReversePrint1(ListNode* phead) { if (phead!=NULL) { if (phead->_next != NULL) { ReversePrint1(phead->_next); } cout << phead->_value << "->"; } } void List::ReversePrint2(ListNode* phead) { stack<ListNode*> s; if (NULL == phead) { return ; } else { ListNode* pCur = phead; while (pCur != NULL) { s.push(pCur); pCur = pCur->_next; } while (!s.empty()) { pCur = s.top(); cout << pCur->_value << "->"; s.pop(); } } } void test() { List l; ListNode* phead; l.InitNode(&phead); l.PushBack(&phead,1); l.PushBack(&phead,3); l.PushBack(&phead,5); l.PushBack(&phead,7); l.PushBack(&phead,9); //l.Print(); //l.ReversePrint1(phead); l.ReversePrint2(phead); } int main() { test(); system("pause"); return 0; }