单位网站怎么制作,分销系统小程序开发,下载网站模板,wordpress管理员与编辑可见面试题5#xff1a;从尾到头打印链表 题目#xff1a;输入一个链表的头结点#xff0c;从尾到头反过来打印出每个结点的值。
链表结点定义如下:
struct ListNode
{int m_nKey;ListNode *m_pNext;
};通常打印是一个只读操作#xff0c;我们不希望打印时修改内容。
假设面…面试题5从尾到头打印链表 题目输入一个链表的头结点从尾到头反过来打印出每个结点的值。
链表结点定义如下:
struct ListNode
{int m_nKey;ListNode *m_pNext;
};通常打印是一个只读操作我们不希望打印时修改内容。
假设面试官也要求这个题目不能改变链表的结构。
接下来我们想到解决这个问题肯定要遍历链表。
遍历的顺序是从头到尾的顺序可输出的顺序却是从尾到头。
也就是说第一个遍历到的结点最后一个输出而最后一个遍历到的结点第一个输出。
这就是典型的“后进先出”我们可以用栈实现这种顺序。
每经过一个结点的时候把该结点放到一个栈中。
当遍历完整个链表后再从栈顶开始逐个输出结点的值此时输出的结点的顺序已经反转过来了。
这种思路的实现代码如下
void PrintListReversingly_Iteratively(ListNode *pHead)
{stackListNode *nodes;ListNode *pNode pHead;while (pNode ! nullptr){nodes.push(pNode);pNode pNode-m_pNext;}while (!nodes.empty()){pNode nodes.top();cout pNode-m_nKey ;nodes.pop();}cout endl;
}既然想到了用栈来实现这个函数而递归在本质上就是一个栈结构于是很自然地又想到了用递归来实现。要实现反过来输出链表我们每访问到一个结点的时候先递归输出它后面的结点再输出该结点自身这样链表的输出结果就反过来了。 基于这样的思路不难写出如下代码
void PrintListReversingly_Iteratively(ListNode *pHead)
{if (pHead ! nullptr){if (pHead-m_pNext ! nullptr){PrintListReversingly_Iteratively(pHead-m_pNext);}cout pHead-m_nKey ;}
}上面的基于递归的代码看起来很简洁但有个问题当链表非常长的时候就会导致函数调用的层级很深从而有可能导致函数调用栈溢出。显式用栈基于循环实现的代码的鲁棒性要好一些。
测试用例 ● 功能测试输入的链表有多个结点输入的链表只有一个结点。 ● 特殊输入测试输入的链表头结点指针为NULL。 本题考点 ● 考查对单项链表的理解和编程能力。 ● 考查对循环、递归和栈3个相互关联的概念的理解。
