1.题目描述
题目:输入一个链表的头结点,从尾到头反过来打印出每一个结点的值,链表结点定义以下:node
struct ListNode { int m_nKey; ListNode* m_pNext; };
2.分析问题面试
一般打印是一个只读操做,咱们不但愿打印时修改内容。假设面试官也要求这个题目不能改变链表的结构。接下来咱们想到解决这个问题确定要遍历链表。遍历的顺序是从头至尾的顺序,可输出的顺序倒是从尾到头。也就是说第一个遍历到的结点最后一个输出,而最后一个遍历到的结点第一个输出。这就是典型的“后进先出”,咱们能够用栈实现这种顺序。每通过一个结点的时候,把该结点放到一个栈中。当遍历完整个链表后,再从栈顶开始逐个输出结点的值,此时输出的结点的顺序已经反转过来了。这种思路的实现代码以下:函数
void PrintListReversingly_Iteratively(ListNode* pHead) { assert(pHead != NULL); std::stack<ListNode*> nodes; ListNode* pNode = pHead; while(pNode != NULL) { nodes.push(pNode); pNode = pNode->m_pNext; } while(!nodes.empty()) { pNode = nodes.top(); std::cout<<pNode->m_nKey<<" "; nodes.pop(); } }
既然想到了用栈来实现这个函数,而递归在本质上就是一个栈结构,因而很天然地又想到了用递归来实现。要实现反过来输出链表,咱们每访问到一个结点的时候,先递归输出它后面的结点,再输出该结点自身,这样链表的输出结果就反过来了。
基于这样的思路,不难写出以下代码: spa
void PrintListReversingly_Recursively(ListNode* pHead) { if(pHead != NULL) { if(pHead->m_pNext != NULL) { PrintListReversingly_Recursively(pHead->m_pNext); } std::cout<<pHead->m_nkey<<" "; } }