建模。用裸指针管理一块堆内存，维护 data_（首地址）、size_（元素数）、cap_（容量）。不变量：\(\text{size\_} \le \text{cap\_}\)，且 data_[0..size_-1] 是有效元素。push_back 时若不变量即将被破坏（size_ 等于 cap_），先倍增再写入。

代码。

#include <cstddef>
#include <cassert>

class DynamicArray {
public:
    DynamicArray() : data_(nullptr), size_(0), cap_(0) {}
    ~DynamicArray() { delete[] data_; }

    // 禁用拷贝，避免双重释放；需要拷贝时按 rule of three 补齐
    DynamicArray(const DynamicArray&) = delete;
    DynamicArray& operator=(const DynamicArray&) = delete;

    void push_back(int value) {
        if (size_ == cap_)
            reserve(cap_ == 0 ? 1 : cap_ * 2);  // 倍增扩容，保证均摊 O(1)
        data_[size_++] = value;
    }

    void reserve(std::size_t newCap) {
        int* fresh = new int[newCap];           // 申请更大的连续内存
        for (std::size_t i = 0; i < size_; ++i)
            fresh[i] = data_[i];                 // 逐个搬运旧元素
        delete[] data_;                          // 释放旧内存
        data_ = fresh;
        cap_ = newCap;
    }

    int& at(std::size_t i) {
        assert(i < size_ && "index out of range");  // fail-fast
        return data_[i];
    }

    std::size_t size() const { return size_; }
    std::size_t capacity() const { return cap_; }

private:
    int* data_;
    std::size_t size_, cap_;
};

数值演示。从空数组开始连 push 1 到 9：容量序列 1 → 2 → 4 → 8 → 16，搬运发生在长度 1、2、4、8 处，总搬运次数 \(1+2+4+8=15\)，小于 \(2 \times 9 = 18\)，与「搬运总量 \(\lt 2n\)」的界吻合。

复杂度。push_back 均摊 \(\Theta(1)\)，单次最坏 \(\Theta(n)\)（触发扩容的那一次）；at 是 \(\Theta(1)\)。若把倍增换成 cap_ + 1，均摊退化为 \(\Theta(n)\)。

边界。初始 cap_ 为 0，首次插入要先分配；拷贝构造若不禁用会造成双重释放；扩容后所有指向旧元素的指针、引用、迭代器全部失效——这是 vector 最著名的坑，面试必须主动提。生产代码中搬运应使用移动或 std::unique_ptr，此处为了展示机制保留最朴素的写法。

面试怎么讲。先讲 size 与 capacity 的分离，再讲倍增，然后用等比数列求和当场推出总搬运 \(\lt 2n\)，最后补一句「单次最坏 O(n)、均摊 O(1)，低延迟场景应 reserve 预分配」——这一句把均摊与最坏的区别讲清楚，通常是加分点。

建模。维护三指针：prev（已反转段的头）、curr（未反转段的头）、nxt（暂存后继防断链）。不变量：每轮开始时，prev 到原头节点的一段已完全反向，curr 到原尾节点的一段方向未动。

代码。

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;   // 已反转链的头
    ListNode* curr = head;      // 未反转链的头
    while (curr != nullptr) {
        ListNode* nxt = curr->next;  // 先存后继，防止断链
        curr->next = prev;           // 反转一条边
        prev = curr;                // 两指针各前进一步
        curr = nxt;
    }
    return prev;                // curr 为空时 prev 即新表头
}

数值演示。链 1 → 2 → 3：第一轮后 1 → nullptr（prev=1），第二轮后 2 → 1（prev=2），第三轮后 3 → 2（prev=3），返回 3，链变为 3 → 2 → 1。

复杂度。时间 \(\Theta(n)\)，每个节点处理一次；空间 \(\Theta(1)\)，只用三个指针。递归版本同样 \(\Theta(n)\) 时间，但递归深度 \(n\) 带来 \(\Theta(n)\) 栈空间，百万级链表会栈溢出——面试要能说出迭代版胜在空间。

边界。空链表（head 为 nullptr，循环不执行，直接返回 nullptr）；单节点（一轮即完，返回原头）。变式追问：每 k 个一组反转——外层再套一个计数循环，组内逻辑与本例完全相同。

面试怎么讲。先在白板写不变量再写代码，讲清「先存 next 再改指向」的动机；主动对比递归解法的空间代价，并指出这是「能徒手写对指针」这一基本功的标准检验题。

建模。两个小问共用同一骨架：慢指针 1 步、快指针 2 步。(a) 快指针触空即停，慢指针停在中点；(b) 两指针相等即有环，快指针触空即无环。

代码。

// (a) 返回中间节点（偶数长度时返回靠后的那个中点）
ListNode* middleNode(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;          // 慢指针 1 步
        fast = fast->next->next;    // 快指针 2 步
    }
    return slow;
}

// (b) Floyd 判圈：有环必相遇
bool hasCycle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;   // 相对速度 1，环内必相遇
    }
    return false;                        // fast 触空，无环
}

数值演示。(a) 链 1 → 2 → 3 → 4 → 5：fast 依次到 3、5 后触空，slow 依次到 2、3，返回 3，正确中点。链 1 → 2 → 3 → 4：初始 slow=fast=1；第一轮 slow=2、fast=3，fast 的下一个存在；第二轮 slow=3、fast 触空，循环停止——偶数长度返回靠后的中点 3。(b) 环 3 → 4 → 5 → 3：slow 进环后两者间距每步缩 1，必在某点重合。

复杂度。两问均为时间 \(\Theta(n)\)、空间 \(\Theta(1)\)。判环的正确性依赖相对速度 1：间距逐次减 1 必到 0，不会跳过。

边界。空链表与单节点（循环条件直接挡掉）；(a) 偶数长度想取靠前的中点时，把 fast 初始化为 head->next 再进循环；(b) 追问续集是「找环入口」——一个指针放回表头，两指针同速前进，再次相遇处即入口，依据是 \(a = (m-1)r + (r-s)\)（见知识点推导）。

面试怎么讲。先把「快指针步数恒为慢指针两倍」这半句说出口，(a) (b) 的正确性就都有了着落；再主动给「找环入口」的推导，这题基本就满分了。

建模。「尾部进、头部出」的容器就是队列（queue）。于是题意是：给你两个队列 A、B，组合出栈的 LIFO 行为。这是源题库里少见的算法设计原题，考察点是「用受限原语搭出另一种秩序」——它的对偶版本「两个栈实现队列」同样必会，本解一并给出，方便对照。

思路（两队列实现栈）。push：直接从 A 尾部进。pop：A 里只剩一个元素时它才是「最后进的」（栈顶），于是把 A 的前 \(n-1\) 个元素依次出队、搬进 B，弹出 A 剩下的那个，再把 A、B 角色互换。任何时刻 B 只是临时缓冲。

代码。

#include <queue>
#include <utility>

class MyStack {
public:
    void push(int x) {
        a_.push(x);                    // 新元素永远从尾部进 A
    }

    int pop() {
        while (a_.size() > 1) {        // 前 n-1 个搬去 B
            b_.push(a_.front());
            a_.pop();
        }
        int top = a_.front();          // 剩下的就是最后进的（栈顶）
        a_.pop();
        std::swap(a_, b_);             // 角色互换，B 变回主容器
        return top;
    }

    bool empty() const { return a_.empty(); }

private:
    std::queue<int> a_, b_;
};

数值演示。push 1、2、3 后 A = [1,2,3]。pop：搬 1、2 进 B，弹 3（正确，3 最后进）。再 pop：搬 1 进 B，弹 2。再 pop：直接弹 1。序列 3、2、1，LIFO 达成。

对偶版（两栈实现队列）与代价对比。栈是「同端进出」，把 in 栈整体倒入 out 栈，顺序恰好翻转一次，两次翻转抵消，恢复 FIFO。关键是只在 out 栈为空时才倒：

#include <stack>

class MyQueue {
public:
    void push(int x) {
        in_.push(x);                        // 只管进
    }

    int pop() {
        if (out_.empty()) transfer();       // out 空了才搬运
        int front = out_.top();
        out_.pop();
        return front;
    }

private:
    void transfer() {
        while (!in_.empty()) {              // in 整体倒进 out
            out_.push(in_.top());
            in_.pop();
        }
    }
    std::stack<int> in_, out_;
};

两个方向的代价不对称，这是本题的面试灵魂：两队列实现栈，每次 pop 都要全量搬运，单次就是 \(\Theta(n)\)；两栈实现队列，每个元素一生至多被搬运一次（in 到 out），\(n\) 次操作总搬运不超过 \(n\)，均摊 \(\Theta(1)\)——又一次聚合法均摊分析。为什么差这么多？因为栈倒进队列方向时顺序「翻转一次」就能复用，而队列倒队列顺序不变、每次 pop 都得重新排队。

复杂度。两队列实现栈：push \(\Theta(1)\)，pop \(\Theta(n)\)。两栈实现队列：push \(\Theta(1)\)，pop 均摊 \(\Theta(1)\)、单次最坏 \(\Theta(n)\)。

边界。对空栈/空队列 pop 必须显式报错而非返回垃圾值；两队列版的 swap 之后 B 必须确认为空，否则状态混乱。变式：用两个栈实现「带 getMin 的栈」——辅助栈同步维护当前最小值，见034 章。

面试怎么讲。先明确「尾部进、头部出 = 队列语义」，画出搬运示意，再主动对比两个方向的均摊复杂度并给出「每个元素至多搬一次」的证明——这道源题的采分点全在对比上。

建模。即对每个下标 i 求「右侧第一个更大的下标 j」并输出 \(j - i\)。暴力对每个 i 向右扫是 \(\Theta(n^2)\)。用单调栈：栈存下标，对应的温度自底向上单调递减；新温度到来时，把栈顶所有更低的下标结算掉。

代码。

#include <vector>
#include <stack>

std::vector<int> dailyTemperatures(const std::vector<int>& t) {
    int n = (int)t.size();
    std::vector<int> ans(n, 0);
    std::stack<int> st;                    // 存下标，温度自底向上递减
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && t[st.top()] < t[i]) {
            ans[st.top()] = i - st.top();  // i 就是栈顶的下一个更暖天
            st.pop();
        }
        st.push(i);
    }
    return ans;                            // 留在栈里的等不到，保持 0
}

数值演示。t = [73, 74, 75, 71, 69, 72, 76, 73]：过程结算顺序为 73←74（1 天）、74←75（1 天）、69←72（1 天）、71←72（2 天）、72←76（1 天）、75←76（1 天），最终答案 [1,1,4,2,1,1,0,0]。

复杂度。每个下标恰好进栈一次、出栈至多一次，外层 for 虽然套着内层 while，总步数仍是 \(\Theta(n)\)，空间最坏 \(\Theta(n)\)（严格递减序列）。

边界。空数组返回空；严格递减输入（如 [75,74,73]）全为 0，栈最终留满；相等温度不算「更高」，比较用严格小于，栈内允许相等元素共存。

面试怎么讲。先说暴力与瓶颈（重复扫描被放弃的次大值），再给「栈里留着的都是还没等到答案的候选」这句直觉，最后强调总代价是进出栈各一次的均摊论证——与例题 1 的扩容分析呼应成一套。