hlwang's Blog

理想主义青年永远不会被现实招安

0%

剑指 Offer 06. 从尾到头打印链表

发表于 分类于
本文字数： 729 阅读时长 ≈ 1 分钟

题目描述

输入一个链表的头节点，从尾到头反过来 返回每个节点的值（用数组返回）。

示例

示例1

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

限制：

1
0 <= 链表长度 <= 10000

思路1

利用递归调用函数到最后时,回逆向返回的特点,保存节点的值

递归代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
    ListNode(int x, ListNode *p) : val(x), next(p) {}
};

class Solution
{
public:
    vector<int> reversePrint(ListNode *head)
    {
        // 定义ans
        vector<int> ans;
        // 调用递归函数
        fun(head, ans);
        // 返回答案
        return ans;
    }
    // 递归函数的参数,是链表和ans,ans采用应用传参,因为需要动态修改ans
    void fun(ListNode *head, vector<int>& ans)
    {
        // 递归结束条件为,head已经到了末尾的nullptr
        // 则返回
        if (head == nullptr)
        {
            return;
        }
        // 递归调用下一个节点
        fun(head->next, ans);
        // 保存当前节点的值
        ans.push_back(head->val);
    }
};