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

难度 简单

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

示例 1：

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

限制：

1
0 <= 链表长度 <= 10000

通过次数277,964

提交次数369,505

思路

辅助栈法：

遍历整个链表，把所有元素压入堆栈中，最后把堆栈中的元素顺序弹出并存储到 Vector 容器中返回

算法流程：
入栈： 遍历链表，将各节点值 push 入栈。

出栈： 将各节点值 pop 出栈，存储于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
27
28
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        int top,i,tmp;
        stack<int> sta;
        ListNode* P = head;
        vector<int> Val;
        while(P)
        {
            sta.push( P->val ); 
            P = P->next;
        }
        while(!sta.empty())
        {
            Val.push_back(sta.top());
            sta.pop();
        }
        return Val;
    }
};

递归法：

利用递归： 先走至链表末端，回溯时依次将节点值加入列表 ，这样就可以实现链表值的倒序输出。

递推阶段： 每次传入 head->next ，以 head == null（即走过链表尾部节点）为递归终止条件，此时直接返回。
回溯阶段： 层层回溯时，将当前节点值加入列表，最后返回即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        if(!head)
            return {};
        vector<int> V = reversePrint(head->next);
        V.push_back(head->val);
        return V;
    }
};