剑指offer - 从尾到头打印链表

发表于 | 更新于

题目

https://www.nowcoder.com/questionTerminal/d0267f7f55b3412ba93bd35cfa8e8035

题意

输入一个链表，从尾到头打印链表每个节点的值。

题解

从尾到头，要访问到链表的尾节点，必须从头开始访问遍历整个链表。在不增加指针的情况下，只能遍历的时候存储每个节点的值，然后倒序输出，可以用栈来实现。当然不存也可以，递归的访问，输出每个点之前先将之后的节点输出。其实也用到了栈，都免不了O(N)的空间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution
{
public:
    vector<int> printListFromTailToHead(ListNode* head)
    {
        stack<int> st;
        while(head!=NULL){
            st.push(head->val);
            head = head->next;
        }
        vector<int> ans;
        while(!st.empty()){
            ans.push_back(st.top());
            st.pop();
        }
        return ans;
    }
};

递归实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution
{
public:
    vector<int> printListFromTailToHead(ListNode* head)
    {
        vector<int> ans;
        dfs(ans,head);
        return ans;
    }
    void dfs(vector<int> &ans,ListNode * head)
    {
        if(head==NULL) return;
        dfs(ans,head->next);
        ans.push_back(head->val);
    }
};