剑指6：从尾到头打印链表

传送门

nowcoder
leetcode

题目描述

输入一个链表，按链表从尾到头的顺序返回每个节点的值（用数组返回）

C++ 代码 - nowcoder

/*
    vector 从前向后保存，然后 reverse

    时间复杂度：O(n)
    空间复杂度：O(n)
*/
vector<int> printListFromTailToHead(ListNode* head) {
    if (head == nullptr) return vector<int>();
 
    vector<int> result;
    while (head != nullptr) {
        result.push_back(head->val);
        head = head->next;
    }
 
    reverse(result.begin(), result.end());
    return result;
}

/*
    使用栈

    时间复杂度：O(n)
    空间复杂度：O(n)
*/
vector<int> printListFromTailToHead(ListNode* head) {
    vector<int> res;
    if (head == nullptr) return res;

    stack<int> s;
    while (head) {
        s.push(head->val);
        head = head->next;
    }
    while (!s.empty()) {
        res.push_back(s.top());
        s.pop();
    }
    return res;
}

/*
    递归

    时间复杂度：O(n)
*/
vector<int> printListFromTailToHead(ListNode* head) {
    if (head == nullptr) return vector<int>();
 
    vector<int> res = printListFromTailToHead(head->next);
    res.push_back(head->val);
    return res;
}

/*
    改变链表结构

    时间复杂度：O(n)
    空间复杂度：O(n)
*/
vector<int> printListFromTailToHead(ListNode* head) {
    ListNode *pre = nullptr;
    ListNode *next = head;
    ListNode *cur = head;
    while (cur) {
        next = cur->next; // 保存当前结点的下一个节点
        cur->next = pre;  // 当前结点指向前一个节点，反向改变指针
        pre = cur;        // 更新前一个节点
        cur = next;       // 更新当前结点
    }
    
    vector<int> res;
    while (pre) {
        res.push_back(pre->val);
        pre = pre->next;
    }
    return res;
}

C++ 代码 - leetcode

/*
    改变链表结构

    时间复杂度：O(n)
    空间复杂度：O(n)
*/
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        ListNode *pre = nullptr, *next = head, *cur = head;
        while (cur) {
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        
        vector<int> res;
        while (pre) {
            res.push_back(pre->val);
            pre = pre->next;
        }
        return res;
    }
};