算法-从尾到头打印链表
算法-从尾到头打印链表
chaibubble
发布于 2018-01-02 11:42:32
发布于 2018-01-02 11:42:32
题目： 输入一个链表，要求从尾到头打印该链表，链表结点定义如下：
struct ListNode
{
int value;
ListNode *next;
};解题思路： 要求很好理解，比如一个链表是：
这里写图片描述
打印的结果是：6 5 4 3 2 1 1.相信大多数人看到这个要求后的第一反应是反转链表，再从头打印，但是这样一来，原始数据就改变了。 2.当然我们可以建立新的内存空间，然后拷贝原链表中的value，毕竟最后要打印的只是value，这样我们就有了一个和原链表的value一样的链表，然后再反转它，这样一来原始数据就不变了，但是这样的操作太过繁琐：遍历拷贝，反转，顺序打印，释放内存的一系列操作在空间和时间复杂度上都消耗较大。 3.既然上一种方法想到了建立新的链表的方式，那么何不建立一个其他的数据结构更简单的完成这件事—栈，这个任务的特点是先遍历到的后打印，我们只需要将先遍历到的结点中的value压入栈中，遍历结束后做出栈操作，这样一来步骤就简化了很多。 4.既然想到了是一种“先遍历后打印，后遍历先打印”的操作，那么可不可以不借助栈来实现这个方法——递归。递归的思想在合并两个排序的链表题目中就使用过，只不过在该题目中我们返回的是最后一次递归的结果，而在本文的题目我们需要打印每一次递归的返回值。
关于思路3和4都是可以的，具体使用哪一个可以根据实际情况来决定，如果链表很长，那么递归调用的层数就会很深，可能导致函数调用栈溢出，用思路3的鲁棒性会更好一些。
代码实现：
//借助栈
void PrintListReversingly_Iteratively(ListNode* pHead)
{
std::stack<ListNode*> nodes;
ListNode* pNode = pHead;
while(pNode != NULL)
{
nodes.push(pNode);
pNode = pNode->next;
}
while(!nodes.empty())
{
pNode = nodes.top();
printf("%d\t", pNode->value);
nodes.pop();
}
}//递归实现
void PrintListReversingly_Recursively(ListNode* pHead)
{
if(pHead != NULL)
{
if (pHead->next != NULL)
{
PrintListReversingly_Recursively(pHead->next);
}
printf("%d\t", pHead->value);
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-08-06 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读