C++之《剑指offer》学习记录（10）：链表

笔者最近在找工作时，无意间读到了一本名为《剑指offer》的书，粗略翻阅了一下，感觉这将会是一本能让我不再苦恼于笔试和面试“手搓代码”的书。故笔者写下该系列博客记录自己的学习历程，希望能和这本书的读者朋友们一起交流学习心得。
介绍：《剑指Offer：名企面试官精讲典型编程题（第2版）》剖析了80个典型的编程面试题，系统整理基础知识、代码质量、解题思路、优化效率和综合能力这5个面试要点。
编程题链接：牛客网在线编程_算法面试_面试必刷TOP101 (nowcoder.com)
本博客关键词：链表，从尾到头打印链表

链表的相关知识可以参考博客：
C、C++常用数据结构：链表-CSDN博客

题设

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

解法一：借助栈

• 时间复杂度：O(n)
• 空间复杂度：O(n)

class Solution {
  public:
    vector<int> printListFromTailToHead(ListNode* head) {
        if (head == nullptr) {
            return {};
        }
        stack<int> sta;
        vector<int> nums;
        ListNode* p = head;
        while (p != nullptr) {
            sta.push(p->val);
            p = p->next;
        }
        while (!sta.empty()) {
            nums.push_back(sta.top());
            sta.pop();
        }
        return nums;
    }
};

链表遍历的顺序是从头到尾的，本题要求的元素输出顺序是从尾到头，这让我们很容易联想到“后进先出”，也就是栈，这里借助C++标准库中的stack容器来完成题目要求。

解法二：递归

• 时间复杂度和空间复杂度由递归算法决定
  递归本质上就是一个栈结构，所以这道题也可以用递归来解，代码也会相对简洁；但是当链表非常长时，会导致函数调用的层次很深，从而可能导致栈溢出的问题，使用解法一代码鲁棒性会更好。

class Solution {
  public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> nums;
        if (head != nullptr) {
            if (head->next != nullptr) {
	            // 递归调用
                nums = printListFromTailToHead(head->next);
            }
            cout << head->val << endl;
            nums.push_back(head->val);
        }
        return nums;
    }
};