剑指Offer-题6-从尾到头打印链表 | Orange's Blog

题目：从尾到头打印链表

输入一个链表的头结点，从尾到头反过来打印每个结点的值。链表结点定义如下：

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

解析

链表不同数组，查找某节点只能老老实实从头遍历。循环倒序遍历需要时间复杂度为O(n^2)，不可取。分如下两种情况优化：

1. 如果可以反转链表，遍历中调整 pNext 指针指向，最后遍历即可。代码如下

   void printListReversely(ListNode *pHead)
   {
       if (nullptr == pHead)
           return;
        ListNode *pNode = nullptr;
        ListNode *pNodeNext = pHead;
        ListNode *pTemp = nullptr;
        while (pNodeNext != nullptr)
        {
            pTemp = pNodeNext->pNext;
            pNodeNext->pNext = pNode;
            pNode = pNodeNext;
            pNodeNext = pTemp;
        }
        while (pNode != nullptr)
        {
            printf("%d\n", pNode->value);
            pNode = pNode->pNext;
        }
   }

2. 如果禁止修改链表，遍历中倒序存储节点内容，最后遍历即可。空间复杂度O(n)、时间复杂度O(n)，此举是以空间换时间。代码如下

   void printListReversely(ListNode *pHead)
   {
       if (nullptr == pHead)
           return;
        std::stack<ListNode*> nodes;
        ListNode *pNode = pHead;
        while (pNode != nullptr)
        {
            nodes.push(pNode);
            pNode = pNode->pNext;
        }
        while (!nodes.empty())
        {
            pNode = nodes.top();
            printf("%d\n", pNode->value);
            nodes.pop();
        }
   }

本文采用 CC BY-NC-SA 3.0 Unported 协议进行许可