力扣×剑O 06.从尾到头打印链表

发表于 更新于 阅读次数： 本文字数： 2.4k 阅读时长 ≈ 2 分钟

剑指 Offer 06. 从尾到头打印链表
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：
输入：head = [1,3,2]
输出：[2,3,1]

限制：
0 <= 链表长度 <= 10000

第一反应的思路很简单，遍历并保存，然后逆序保存并返回另一个数组。很明显虽然时间、空间代价O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <vector>
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> vals,reverVals;
        int num=0;
        while(head!=NULL){
            vals.push_back(head->val);
            ++num;
            head=head->next;
        }
        //reverse(res.begin(),res.end());
        //后面才知道上面的函数，一行代码就可以代替下面的循环，还省了一个数组的空间
        while(num!=0){
            reverVals.push_back(vals[num-1]);
            --num;
        }
        return reverVals;
    }
};

稍微想一下还可以有个略微好点的方案：用前后两个指针，遍历的时候把前一个结点和当前节点逆转，最后遍历完之后再反过来遍历一遍，保存到一个数组。仍然时间、空间代价O(n))，但好处是节省了一个大小为n的数组的空间开销。

书上再一次强调，要分情况，因为原来的链表不一定允许被修改。

看到这道题后 ， 很多人的第一 反应是从头到尾输出将会 比 较简单，于是我们很自然地想到把链表中链接节点的指针反转过来 ，改变链表的方向，然后就可以从头到 尾输出了 。 但该方法会改变原来链表的结构 。是否允许在打印链表的时候修改链表的结构？这取决千面试官的要求，因此在面试的时候我们要询问清楚面试官的要求 。

书上的第一个例子和我的代码思路相同，同样是用了先进后出的性质，但我只是用数组模拟了这种特点，书上用了真正的栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Print ListReversingly_lteratively(ListNode* pHead)
{
    std: :stack<ListNode*> nodes:

    Li stNode* pNode = pl-lead:
    while(pNode != nullptr){
        nodes.push(pNodc);
        pNodc = pNode->m_pNext;
     }
    while(!nodes.empty())
    {
    pNode = nodes.top(),
    printf("¾d\t", pNode->m_nValue);
    nodes.pop();
    }   
}

第二个解法我是想不出的，不理解“递归在本质上就是 一个栈结构”这句话。

既然想到了用栈来实现这个函数，而递归在本质上就是 一个栈结构 ，于是很自然地又想到了用递归来实现 。 要实现反过来输出链表 ，我们每访问到 一个节点的时候 ， 先递归输出它后面 的节点 ， 再输 出该节点自身 ，这样链表的输出结果就反过来了 。

网上查了一下，大概是因为：

当递归调用时每次调用自己时可以看做是压栈过程，当递归条件满足结束时，递归一级一级的返回时可以看做是出栈的过程。

我自己的理解是：每次函数自己调用自己的时候相当于一级一级按顺序把旧的状态、新的状态依次放入栈中，等到到达了底层开始返回，那么就开始从最上层最新的状态开始逐级恢复，也就是出栈。

后面的代码很容易理解，写起来也很容易

1
2
3
4
5
6
7
8
9
10
11
12
/*
该题是书上的，没有力扣上对格式等的要求，因为如果下面代码拿去做题需要改动
*/
void PrintlistReversingly_Recursively(ListNode* pHead)
{
    if (pHead'= nullptr)//pHead不为空，确保现在的节点不是最后一个
    {
    if (pHead->m__pNext != nullptr)//pHead的下一个不为空，确保还可以以pHead->m__pNcxt继续递归
        PrintlistRevcrsingly_ Recursively(pHead->m__pNext);
    printf("¾d\t" , pHead->m_nValue;//递归到底后，输出值
    }
}

第二种方法存在的问题是：

当链表非常长的时候 ， 就会导致函数调用的层级很深 ，从而有可能导致函数调用栈溢出 。显然用栈基千循环实现的代码的鲁棒性要好 一 些 。

评论区给出了另一种方法：不用栈，不用递归。核心思想在于遍历两次链表，第一次遍历只记录个数，第二次遍历时逆序保存数据到同样大小数组中，遍历完成后最后返回数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
std::vector<int> Solution::reversePrint(const ListNode* head)
{
    const ListNode* node = head;
    std::size_t count = 0;
    while (node != nullptr) {
        ++count;
        node = node->next;
    }
    std::vector<int> nums(count);  // 预分配 count 个空间。
    node = head;
    for (auto i = nums.rbegin(); i != nums.rend(); ++i) {
        *i = node->val;
        node = node->next;
    }
    return nums;
}