算法-从尾到头打印链表

chaibubble

发布于 2018-01-02 11:42:32

5690

发布于 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 删除

编程算法