题目大意:
输入一个链表的头结点,按照 从尾到头 的顺序返回节点的值。
返回的结果用数组存储。
数据范围:
$0\leq链表长度\leq1000$。
样例:
输入:[2, 3, 5]
返回:[5, 3, 2]
接下来向大家介绍两种思路,第一种是普通的循环,第二种是非尾部递归。
$NO.1$ 循环
没啥好说的,定义一个vector
,循环把链表中的所有数都存进去。由于题目要求倒序,就再把vector
反转了,return
这个vector
。
代码:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
vector<int> printListReversingly(ListNode* head) {
vector<int> v;
//循环遍历链表
while (head)
{
v.push_back(head->val);
head = head->next;
}
reverse(v.begin(), v.end());//别忘了翻转
return v;
}
};
$NO.2$ 非尾部递归
递归有两种形式,第一种是尾递归,第二种叫非尾部递归。
通俗来讲,尾递归是正序的,将输出语句放在递归语句的前面;而非尾部递归是逆序的,把输出语句放到递归语句的后面。
再来分析一下这道题,“从尾到头”很明显是逆序的,所以使用非尾部递归。
代码:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
vector<int> v;//设成全局变量更方便
void print(ListNode* cur) {
//非尾部递归
if (cur == NULL) return;
print(cur->next);
v.push_back(cur->val);
}
vector<int> printListReversingly(ListNode* head) {
print(head);
return v;
}
};
如果把上述代码中的print
改成尾递归就是:
void print(ListNode* cur) {
if (cur == NULL) return;
v.push_back(cur->val);
print(cur->next);
}
这样就成了正序。
那这篇题解到这里就结束了,看在我讲的这么详细的份上,能给我个赞吗?谢谢啦~~
$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\mathcal{writer\enspace by \enspace acwing}$ : $\mathfrak{天元之弈}$