[AcWing]17. 从尾到头打印链表

输入一个链表的头结点，按照 从尾到头 的顺序返回节点的值。

返回的结果用数组存储。

数据范围

0 ≤ 链表长度 ≤ 1000。

样例

1
2
输入：[2, 3, 5]
返回：[5, 3, 2]

算法思想

最简单的方法就是，直接遍历链表，然后存入vector，再利用库函数将其反转输出。
所以此处只写一下，递归函数法。
还是利用递归栈，出栈的时候将节点值塞入vector，这样就是逆序的了。

代码实现

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> res;
    
    void dfs(ListNode * head){
        // 出口
        if(!head) return;
        // 找到尾
        dfs(head -> next);
        // 从尾到头放入res
        res.push_back(head -> val);
    }

    vector<int> printListReversingly(ListNode* head) {
        dfs(head);
        return res;
    }
};

思考

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> ans;

    vector<int> printListReversingly(ListNode* head) {
        // 如果已经遍历到末尾，先创建一个空集合，为逆向存储元素做准备
        if(!head) return {}; 
        // 压栈
        printListReversingly(head -> next);
        // 出栈的时候
        ans.push_back(head -> val);
        
        return ans;
    }
};

假设链表元素是：[1, 2]。

它的函数调用栈压栈顺序是：printListReversingly(1)、printListReversingly(2)、printListReversingly(NULL)。

它的出栈顺序是：printListReversingly(NULL)、printListReversingly(2)、printListReversingly(1)

当执行到printListReversingly(2)的时候，ans.push_back(2)之后，接下来会执行return ans，那么为什么没有终止掉递归？

答：因为return ans只是终止掉了属于printListReversingly(2)的这一层递归，还剩printListReversingly(1)的递归。最终ans里面的元素会是[2, 1]。

对于这道题来说，外部肯定有一个变量接收最后的ans = [2, 1]。

第二个问题来了同时也是最重要的一个问题：

为什么printListReversingly函数在递归过程中返回了多次，为什么第一次返回的时候没有将集合传给外部那个变量？

答：因为当最初的调用者接收到返回值时，所有的递归调用都已经完成，并且ans已经包含了所有逆序的元素

类似于main函数中写：auto a = printListReversingly(list);，当a收到返回的ans的时候，函数递归早已经结束了。

有如下规律：

1
2
3
4
5
6
7
第一次递归调用
第二次递归调用
第二次递归返回
第一次递归返回
主 printListReversingly 函数调用返回
auto a = [2, 1];
是一气呵成的！！！