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

</br></br>

题目：

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

示例：

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

限制：

0 <= 链表长度 <= 10000

</br></br>

思路一：

使用reverse函数完成链表的逆序打印。我们通过遍历将链表中的值插入数组中，然后使用reverse完成数组元素的翻转，对数组元素翻转之后打印出的数组元素顺序即是链表从尾到头打印的顺序。

代码如下：

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> v;
        ListNode* cur = head;
        while(cur)
        {
            v.push_back(cur->val);
            cur = cur->next;
        }
        //reverse函数的时间复杂度为O(N)
        reverse(v.begin(),v.end());
        return v;
    }
};

时间复杂度：O(N)

空间复杂度：O(N)

</br></br>

思路二：

我们可以通过修改链表中next指针的指向，先将链表反转，假设原链表为1->2->3->4->5->nullptr，反转后为5->4->3->2->1->nullptr；然后我们再申请一个数组，通过遍历新链表中的值放入数组中，此时数组中的值就已经是原链表中从尾到头的值。

链表的反转过程如下：

代码如下：

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> v;
        ListNode* cur = head; //当前节点
        ListNode* prev = nullptr;//前一个节点
        
        //链表的反转
        while(cur)
        {
            ListNode* tmp = cur->next;
            cur->next = prev;
            prev = cur;
            cur = tmp;
        }
        //此时prev就是链表的头节点
        cur = prev;
        //再从新链表的头节点开始遍历插入数组中
        while(cur)
        {
            v.push_back(cur->val);
            cur = cur->next;
        }
        return v;
    }
};

时间复杂度：O(N)

空间复杂度：O(N)

</br></br>

思路三：

根据栈的先进后出的特性，使用栈完成链表的逆序打印。先遍历链表将链表中的值压入栈中，然后再通过top函数和pop函数将栈中的数据依次放入数组中，即可完成链表的逆序打印。

代码如下：

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> v;
        stack<int> st;
        ListNode* cur = head;
        //将链表中的值压入栈中
        while(cur)
        {
            st.push(cur->val);
            cur = cur->next;
        }
        //将栈中的值依次放入数组中
        while(!st.empty())
        {
            v.push_back(st.top());
            st.pop();
        }
        return v;
    }
};

时间复杂度：O(N)

空间复杂度：O(N)