算法-从尾到头打印链表

谁践踏了优雅 2022-06-10 00:15 125阅读 0赞

**题目：**  
输入一个链表，要求从尾到头打印该链表，链表结点定义如下：

struct ListNode
    {
      int value;
      ListNode *next;
    };

**解题思路：**  
要求很好理解，比如一个链表是：  
![这里写图片描述][SouthEast]  
打印的结果是：6 5 4 3 2 1  
1.相信大多数人看到这个要求后的第一反应是[反转链表][Link 1]，再从头打印，但是这样一来，原始数据就改变了。  
2.当然我们可以建立新的内存空间，然后拷贝原链表中的value，毕竟最后要打印的只是value，这样我们就有了一个和原链表的value一样的链表，然后再反转它，这样一来原始数据就不变了，但是这样的操作太过繁琐：遍历拷贝，反转，顺序打印，释放内存的一系列操作在空间和时间复杂度上都消耗较大。  
3.既然上一种方法想到了建立新的链表的方式，那么何不建立一个其他的数据结构更简单的完成这件事—栈，这个任务的特点是先遍历到的后打印，我们只需要将先遍历到的结点中的value压入栈中，遍历结束后做出栈操作，这样一来步骤就简化了很多。  
4.既然想到了是一种“先遍历后打印，后遍历先打印”的操作，那么可不可以不借助栈来实现这个方法——**递归**。递归的思想在[合并两个排序的链表][Link 2]题目中就使用过，**只不过在该题目中我们返回的是最后一次递归的结果，而在本文的题目我们需要打印每一次递归的返回值。**

关于思路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);
        }
    }

[SouthEast]: /images/20220610/2f11ef5e8ce34a86a43c6beefcd0f05f.png
[Link 1]: http://blog.csdn.net/chaipp0607/article/details/76457247
[Link 2]: http://blog.csdn.net/chaipp0607/article/details/76622563