链表、双端队列与单调结构 - 面试题

#

★★★

1. 删除链表的倒数第 N 个节点（LeetCode 19）中双指针间距 N 的一次遍历法，如何处理删除头节点的边界

问题

给定一个单链表，要求删除其倒数第 N 个节点，并说明如何使用双指针在一次遍历中完成，以及如何处理删除头节点时的边界情况？

考察点

双指针间距 N 的滑动技巧
虚拟头节点（dummy node）的边界处理
指针操作的正确性

答案

使用两个指针 fast 和 slow，先让 fast 前进 N 步，使 fast 与 slow 之间相隔 N 个节点；然后 fast 和 slow 同时前进，当 fast 到达链表末尾时，slow 恰好指向倒数第 N 个节点的前一个节点，此时修改 slow.next 即可完成删除。为了让删除头节点也能统一处理，可在链表前加一个虚拟头节点 dummy，slow 从 dummy 出发，这样 fast 与 slow 之间始终隔 N 个节点，fast 到末尾时 slow 正好在待删节点的前驱，无需特判头节点。

解析

关键是把"倒数第 N 个"转化为"与末尾相差 N-1 个节点"，通过固定间距让慢指针停在待删节点的前驱。若不使用 dummy，删除头节点时前驱为 null，需要单独判断，容易出错；dummy 使所有情况统一。

示例代码

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head);
    ListNode fast = dummy, slow = dummy;
    for (int i = 0; i < n; i++) fast = fast.next;
    while (fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return dummy.next;
}

#

★★★

2. 单调队列如何 O(1) 均摊维护滑动窗口最大值（LeetCode 239），双端队列存候选下标、队首淘汰过期元素、队尾淘汰更小元素

问题

给定数组和一个大小 k 的滑动窗口，说明如何用单调队列在 O(1) 均摊时间维护窗口最大值，并解释双端队列中存下标而非值的意义？

考察点

单调队列维护候选下标的原理
队首淘汰过期元素、队尾淘汰更小元素两条规则
O(1) 均摊复杂度的来源

答案

用一个双端队列 deque 存数组下标，维护从队首到队尾严格递减的对应值。每次加入新元素时：先淘汰队首中已滑出窗口（下标 < i-k+1）的过期元素；然后在队尾把对应值小于等于当前值的元素全部弹出（新元素更大且更晚出现，旧元素不可能再成为最大值），最后把当前下标入队。于是队首始终是当前窗口最大值，每次滑动均摊 O(1)。

解析

每个元素最多入队一次、出队一次，因此总操作 O(n)，摊到每个窗口 O(1)。存下标是为了能判断元素是否过期，若只存值则无法确定元素是否仍在窗口内。

示例代码

public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] res = new int[n - k + 1];
    Deque<Integer> dq = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        while (!dq.isEmpty() && dq.peekFirst() < i - k + 1) dq.pollFirst();
        while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast();
        dq.offerLast(i);
        if (i >= k - 1) res[i - k + 1] = nums[dq.peekFirst()];
    }
    return res;
}

#

★★★

3. 单链表归并排序如何实现 O(n log n) 时间 O(1) 空间？自顶向下与自底向上两种写法的取舍

问题

说明如何对单链表实现归并排序，达到 O(n log n) 时间，并比较自顶向下与自底向上两种写法的空间复杂度与取舍？

考察点

链表归并排序的 O(n log n) 分析
找中点（快慢指针）与合并两个有序链表
自顶向下（递归 O(log n) 栈空间）与自底向上（迭代 O(1) 空间）的差异

答案

归并排序对链表同样适用：把链表分成两半，分别排序后合并。自顶向下版本用快慢指针找中点分割，递归地对左右两半排序再合并，除递归栈外无需额外数组，空间 O(log n)；自底向上版本从长度为 1 的子链表开始，两两合并逐渐翻倍长度，全程迭代，空间 O(1)。链表与数组不同，无需额外 O(n) 空间归并，因为可以通过重排指针原地合并。

解析

数组归并排序需要 O(n) 辅助数组，链表则通过指针重排实现 O(1) 额外存储（归并过程本身不分配新节点）。自顶向下代码更简洁但递归栈深 O(log n)；自底向上略复杂但真正 O(1) 空间，且对迭代器/外部存储更友好。

示例代码

public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next; fast = fast.next.next;
    }
    ListNode mid = slow.next;
    slow.next = null;
    return merge(sortList(head), sortList(mid));
}
private ListNode merge(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(0), p = dummy;
    while (a != null && b != null) {
        if (a.val <= b.val) { p.next = a; a = a.next; }
        else { p.next = b; b = b.next; }
        p = p.next;
    }
    p.next = a != null ? a : b;
    return dummy.next;
}

#

★★★

4. 合并 K 个有序链表的最优复杂度是多少，优先队列与分治两种实现如何取舍？

问题

给定 K 个有序链表，说明合并它们的最优时间复杂度，并比较优先队列（堆）与分治归并两种实现方式的取舍？

考察点

合并 K 个有序链表的最优复杂度 O(N log K)
优先队列（小根堆）思路
分治两两合并的思路与复杂度

答案

设总节点数为 N、链表数为 K。最优复杂度为 O(N log K)。优先队列法：把 K 个链表的头节点放入小根堆，每次弹出最小节点放入结果，并把它所在链表的下一节点压入堆，重复 N 次，每次堆操作 O(log K)，总 O(N log K)。分治法：每次两两合并，需要 log K 轮，每轮合并总节点数 O(N)，总 O(N log K)。两者时间复杂度相同，但堆实现代码更直接、常数略大；分治实现的空间 O(log K)（递归栈）且无需额外堆结构。

解析

O(N log K) 是下界，因为每取一个元素都要在 K 个候选间比较。堆法每步弹出的最小元素即当前 K 个链头的最小值，保证全局有序；分治则把问题归约为两两归并，工程上更易实现。

示例代码

public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
    for (ListNode h : lists) if (h != null) pq.offer(h);
    ListNode dummy = new ListNode(0), p = dummy;
    while (!pq.isEmpty()) {
        ListNode t = pq.poll();
        p.next = t; p = p.next;
        if (t.next != null) pq.offer(t.next);
    }
    return dummy.next;
}

#

★★★

5. 实现带随机指针链表的深拷贝，要求 O(n) 时间 O(1) 额外空间（原题 138），说明'插入-拆链'三步法的正确性

问题

给定一个带 next 和 random 指针的链表，说明如何实现 O(n) 时间、O(1) 额外空间（忽略新节点本身）的深拷贝，并证明"插入-拆链"三步法的正确性？

考察点

深拷贝的定义与随机指针的难点
插入-拆链三步法（复制节点、映射 random、拆分为两条链）
O(n) 时间 O(1) 额外空间的正确性

答案

三步法：第一步，遍历原链表，在每个节点后面插入一个值相同的副本节点；第二步，再次遍历，把每个副本节点的 random 指向其原节点的 random 的后继（即原节点 random 指向的节点的副本）；第三步，把链表拆成两条独立链表，原节点连原节点、副本节点连副本节点，返回副本链头。这样副本节点的 random 映射通过物理相邻关系由原节点推导，无需哈希表，达到 O(1) 额外空间。

解析

若用哈希表需 O(n) 空间。插入-拆链法把"原节点→副本节点"的映射内嵌在链表结构里，用原节点.next 即副本节点，从而在 O(1) 空间内完成 random 的复制。所有节点只遍历常数次，故时间 O(n)。

示例代码

public Node copyRandomList(Node head) {
    if (head == null) return null;
    for (Node p = head; p != null; p = p.next.next) {
        Node copy = new Node(p.val);
        copy.next = p.next;
        p.next = copy;
    }
    for (Node p = head; p != null; p = p.next.next) {
        if (p.random != null) p.next.random = p.random.next;
    }
    Node res = head.next;
    for (Node p = head; p != null; ) {
        Node copy = p.next;
        p.next = copy.next;
        p = copy.next;
        if (copy.next != null) copy.next = copy.next.next;
    }
    return res;
}

#

★★★

6. 用两个栈实现队列的均摊 O(1) 入队/出队，输出栈空时整堆翻转，势能法证明均摊代价

问题

说明如何用两个栈实现队列，使入队和出队均摊 O(1)，并用势能法证明均摊代价？

考察点

输入栈与输出栈的分工
输出栈空时整堆翻转（transfer）的触发时机
势能法证明均摊 O(1)

答案

维护两个栈 inStack 和 outStack。入队时把元素压入 inStack（O(1)）。出队时若 outStack 非空，直接弹出；若 outStack 为空，则把 inStack 中所有元素依次弹出并压入 outStack，使元素顺序反转，再弹出 outStack 栈顶。每个元素恰好被移入 inStack 一次、翻转到 outStack 一次、从 outStack 弹出一次，因此每个元素最多经历常数次操作，均摊 O(1)。

解析

势能法：设势函数 Φ = inStack.size()。入队压入一个元素使 Φ 增 1，实际代价 1，摊还代价 = 1 + ΔΦ = 2；出队时若需翻转，把 inStack 的 k 个元素移到 outStack，实际代价 k，但此时 Φ 从 k 降到 0，ΔΦ = -k，摊还 = k - k = 0。因此每次操作摊还代价为常数，均摊 O(1)。

示例代码

class MyQueue {
    Deque<Integer> in = new ArrayDeque<>(), out = new ArrayDeque<>();
    public void push(int x) { in.push(x); }
    public int pop() {
        if (out.isEmpty()) while (!in.isEmpty()) out.push(in.pop());
        return out.pop();
    }
    public int peek() {
        if (out.isEmpty()) while (!in.isEmpty()) out.push(in.pop());
        return out.peek();
    }
    public boolean empty() { return in.isEmpty() && out.isEmpty(); }
}

#

★★★

7. 链表插入排序与数组插入排序的复杂度差异中为何链表不需要移动元素但仍为 O(n²)

问题

说明链表插入排序与数组插入排序的复杂度差异，解释为什么链表插入不需要移动元素却仍为 O(n²)？

考察点

插入排序的基本思想
数组版本需要移动元素、链表版本只需改指针
两种版本都是 O(n²) 的原因

答案

插入排序对每个元素，在已排序部分找到合适位置并插入。数组版本需要把插入位置之后的所有元素后移一位，最坏 O(n) 移动；链表版本通过修改指针把新节点插入，无需移动任何元素，插入本身 O(1)。但无论哪种，找到插入位置都需要在已排序部分线性扫描，最坏 O(n)，因此总复杂度仍为 O(n²)。链表节省的是"移动元素"的常数因子，并没有改变比较次数这一主导因素。

解析

复杂度上界由比较次数决定，而非移动次数。链表插入排序比较次数与数组相同，最坏情况（逆序输入）每次都要扫描整个已排序部分，共 n(n-1)/2 次比较，故 Θ(n²)。链表只是消除了移动开销，常数更小。

示例代码

public ListNode insertionSortList(ListNode head) {
    ListNode dummy = new ListNode(0);
    ListNode cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        ListNode p = dummy;
        while (p.next != null && p.next.val < cur.val) p = p.next;
        cur.next = p.next;
        p.next = cur;
        cur = next;
    }
    return dummy.next;
}

#

★★

8. 单链表每 k 个一组反转（LeetCode 25）中当剩余不足 k 时保持原序，给出迭代与递归两种实现并比较栈深

问题

说明如何将单链表每 k 个节点一组反转，当剩余不足 k 个时保持原序，并给出迭代与递归两种实现并比较其递归深度？

考察点

每 k 个一组反转的区间处理
剩余不足 k 则不反转的边界判断
迭代与递归实现的栈深差异

答案

每次取一段长度 k 的区间做局部反转，若剩余不足 k 则直接返回剩余部分。迭代法：用一个 dummy 头，维护区间前驱 pre 和区间首节点，先判断区间是否够 k 个，够则反转 k 个并重新连接 pre，然后移动 pre 到区间末尾继续。递归法：对当前头，先检查剩余是否够 k，不够则原样返回；够则反转这 k 个，然后用递归处理剩余部分并接在后面。递归版深度为链表段数 O(n/k)，迭代版深度为 O(1)。

解析

迭代版需要额外记录长度判断，注意 pre 的移动位置；递归版实现更简洁，其递归深度为 n/k（对 k 段）而非 n，所以在 k 较大时栈深可控，但纯递归仍是 O(n/k)，迭代版空间更优。

示例代码

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode cur = head;
    int count = 0;
    while (cur != null && count < k) { cur = cur.next; count++; }
    if (count < k) return head; // 不足 k 保持原序
    ListNode prev = null, now = head;
    while (count-- > 0) {
        ListNode nxt = now.next;
        now.next = prev;
        prev = now;
        now = nxt;
    }
    head.next = reverseKGroup(now, k); // 递归处理剩余
    return prev;
}

#

★★

9. 如何判断单链表是否回文？要求 O(n) 时间 O(1) 空间，找中点+反转后半+比较+恢复

问题

说明如何判断单链表是否为回文，要求 O(n) 时间、O(1) 空间，并描述找中点、反转后半、比较、恢复的完整过程？

考察点

快慢指针找中点
反转后半链表
比较后恢复原链表

答案

用快慢指针找到中点（快指针走两步、慢指针走一步，快指针到末尾时慢指针在中点）；把慢指针之后的后半段反转；然后两个指针从两端同步比较，若所有对应值相等则是回文；最后把反转的后半段再反转回来恢复原链表。全程只需指针操作，空间 O(1)，时间 O(n)。

解析

由于链表不支持随机访问，判断回文需借助反转。反转后半段后，前半段正序、后半段逆序，逐节点比较即可。比较完恢复原链表是为了不影响后续使用（工程上常要求不破坏输入）。

示例代码

public boolean isPalindrome(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next; fast = fast.next.next;
    }
    ListNode rev = reverse(slow);
    ListNode p = head, q = rev;
    while (q != null) { if (p.val != q.val) return false; p = p.next; q = q.next; }
    reverse(rev); // 恢复
    return true;
}

#

★★

10. 给定两个无环单链表，设计 O(1) 空间判断它们是否相交并找出第一个交点，给出正确性证明（长度差+双指针追赶）

问题

给定两个无环单链表，设计 O(1) 空间算法判断它们是否相交，若相交找出第一个交点，并给出正确性证明？

考察点

长度差法 / 双指针追赶法
相交链表尾部必须重合的性质
O(1) 空间的正确性

答案

方法一（长度差法）：先分别求出两条链表长度 lenA、lenB，让长链的指针先走 |lenA-lenB| 步，然后两指针同步前进，第一个相等的节点即交点。方法二（双指针追赶法）：两个指针 a、b 分别从 A、B 头出发，前进到末尾后各自跳到对方链表头部继续走，由于两指针走过的总路程在相遇时相等（都走完 A+B），必然在交点（或 null）处相遇。正确性：若两链表相交，从交点开始到末尾的节点完全相同，所以总长度差只出现在交点之前，让长链先走长度差即可对齐。

解析

双指针追赶法巧妙之处在于：a 走完 A 后走 B，b 走完 B 后走 A，两指针路程差被抹平，当它们都各走了 (A 的长度 + B 的长度) 内等量路程时，会在交点或 null 相遇。空间 O(1)，时间 O(n)。

示例代码

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode a = headA, b = headB;
    while (a != b) {
        a = a == null ? headB : a.next;
        b = b == null ? headA : b.next;
    }
    return a;
}

#

★★

11. LFU 缓存（LeetCode 460）的频次桶设计中需要'频次→同频节点双向链表'，minFreq 的维护如何做到 O(1)？

问题

说明 LFU（最不经常使用）缓存的设计，为什么需要"频次→同频节点双向链表"的结构，以及 minFreq 如何维护为 O(1)？

考察点

LFU 淘汰策略（频次最低者优先）
频次桶 + 同频节点双向链表的层级结构
minFreq 指针的 O(1) 维护

答案

LFU 需要同时支持 O(1) 的访问、插入和"淘汰频次最低且最早未使用的节点"。因此设计为：哈希表 key→node 快速定位；每个频次对应一个双向链表（LRU 顺序），链表内按最近使用排序；再维护一个频次→链表的映射 freqMap。访问某个 key 时，把它从当前频次链表移除并插入 freq+1 链表，链表的插入删除都是 O(1)。minFreq 维护：当某频次链表变空且它等于当前 minFreq 时，minFreq 递增；当插入新节点（频次=1）时 minFreq 重置为 1。均摊 O(1)。

解析

双向链表保证同频节点间按 LRU 顺序排列，删除"最久未用"的节点在链表尾部 O(1)。minFreq 只在"空桶且等于当前最小"时递增，否则不变化，因此无需扫描，O(1) 维护。

#

★★

12. LRU 缓存为什么用"哈希表+双向链表"，数组实现为什么不可行？

问题

说明 LRU（最近最少使用）缓存为什么用"哈希表+双向链表"实现，以及为什么用数组实现不可行？

考察点

LRU 淘汰策略（最近最少使用优先）
哈希表+双向链表的结构与 O(1) 操作
数组实现无法 O(1) 移动节点

答案

LRU 需要 O(1) 完成 get（更新访问顺序）和 put（插入并淘汰最久未用）。哈希表提供 key→节点 O(1) 定位；双向链表按访问时间从最新到最旧排列，链表头表示最近使用、尾表示最久未用。访问或更新时，把节点移到链表头 O(1)；淘汰时删除尾节点 O(1)。数组不可行：因为移动/删除/插入需要 O(n) 的移位，且无法在 O(1) 内把"刚访问的节点"调整到最前，数组的随机访问优势在这里用不上。

解析

双向链表的关键是能 O(1) 删除任意已知节点（通过前驱指针），配合哈希表 O(1) 定位节点，三者结合使 get/put 都 O(1)。数组虽然访问 O(1)，但调整顺序需要整体移动，退化为 O(n)。

示例代码

class LRUCache {
    LinkedHashMap<Integer, Integer> map;
    int cap;
    public LRUCache(int capacity) { cap = capacity; map = new LinkedHashMap<>(cap, 0.75f, true); }
    public int get(int key) { return map.getOrDefault(key, -1); }
    public void put(int key, int value) {
        map.put(key, value);
        if (map.size() > cap) {
            Integer lru = map.keySet().iterator().next();
            map.remove(lru);
        }
    }
}

#

★

13. Floyd 判环算法中，快慢指针相遇后，为何把一个指针移回 head 同速前进能在环入口相遇？给出严格的模长推导

问题

在 Floyd 判环算法中，说明快慢指针第一次相遇后，为什么把一个指针移回 head 同速前进就能在环入口相遇，并给出严格的模长推导？

考察点

快慢指针第一次相遇的位置
环入口的模长关系推导
同速前进后相遇的数学依据

答案

设链表头到环入口的距离为 a，环入口到第一次相遇点的距离为 b，环长为 L。慢指针走了 a+b，快指针走了 2(a+b)，且快指针比慢指针多走了若干圈，即 2(a+b) - (a+b) = a+b = kL（k 为整数）。移回 head 的指针从位置 0 出发，慢指针从相遇点出发，两者同速前进。当探索指针走了 a 步到达环入口时，慢指针从相遇点走了 a 步，即 b + a = kL 步到达环入口（因为 a+b=kL，模 L 为 0），所以两者在环入口相遇。

解析

关键结论是 a+b 是环长的整数倍。因此从相遇点继续走 a 步，恰好回到环入口；探索指针从 head 走 a 步也到环入口，二者同速则必然在入口首次相遇。该推导依赖"相遇点在环内、环长 L、a+b 为 L 的倍数"。

#

★

14. 两个用逆序链表表示的非负整数相加（LeetCode 2）中如何处理进位与不等长，若改为正序存储（最高位在前）如何解决

问题

说明如何将两个用逆序链表表示的非负整数相加，处理进位与不等长，并讨论若改为正序存储（最高位在前）时的解法？

考察点

逆序链表逐位相加与进位
不等长与最高位额外进位的处理
正序存储时借助栈或反转

答案

逆序链表（最低位在前）恰好符合逐位相加顺序：两个指针同时遍历，逐位相加并记录进位 carry，结果节点的值为 (a+b+carry)%10，carry 更新为 (a+b+carry)/10。某链表为空时该位视为 0；遍历结束后若 carry 仍为 1，则需追加一个值为 1 的最高位节点。若改为正序存储（最高位在前），无法直接从头逐位相加，因为低位对齐需要先到末尾，可用两个栈分别压入两链表节点，从栈顶（最低位）逐位相加，或在相加前先反转两条链表。

解析

逆序存储天然对齐最低位，省去对齐问题。正序存储需借助栈实现从低位到高位计算，或者在结果尾部插入。关键点都是正确传递进位并处理最终多出的最高位。

示例代码

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), p = dummy;
    int carry = 0;
    while (l1 != null || l2 != null || carry != 0) {
        int sum = carry;
        if (l1 != null) { sum += l1.val; l1 = l1.next; }
        if (l2 != null) { sum += l2.val; l2 = l2.next; }
        carry = sum / 10;
        p.next = new ListNode(sum % 10);
        p = p.next;
    }
    return dummy.next;
}

#

★

15. 快慢指针求链表环的长度中相遇后继续同速前进到再次相遇的步数即环长，与 Floyd 判环入口推导的关联？

问题

说明如何用快慢指针求链表环的长度，解释相遇后同速前进到再次相遇的步数即环长，并与 Floyd 判环入口推导建立关联？

考察点

相遇后固定指针同速前进测环长
相遇点出发再回到相遇点需走一圈
与 Floyd 判环入口推导的联系

答案

使用快慢指针判环，首次相遇后，固定一个指针不动（或让两者同速前进），另一个指针从相遇点继续前进并计数。由于相遇点位于环上，从环上某点出发同速绕一圈会再次回到该点，所以再次相遇时走过的步数恰为环长 L。若采用"一个指针不动、另一个绕一圈回来"的方式，步数即环长；若两者同速从相遇点出发，则相对速度为 0 不会相遇，因此通常固定一个，让另一个绕一圈。

解析

与 Floyd 判环入口推导的联系：判环入口用到 a+b = kL（a 为头到入口距、b 为入口到相遇点距、L 为环长），其中 L 就是环长。测环长时，从相遇点出发绕一圈回到相遇点，走的路程正好是 L，与推导中"a+b 是 L 的整数倍"的 L 一致。两者共用"相遇点 + 环长"这一核心概念。

#

★

16. 如何判断链表是否存在环并找到环入口，要求 O(1) 空间（快慢指针法证明）？

问题

说明如何用 O(1) 空间判断链表是否存在环，若存在则找到环入口，并证明快慢指针法的正确性？

考察点

快慢指针判环
环入口的数学推导
O(1) 空间复杂度

答案

快指针每次走两步、慢指针每次走一步。若链表无环，快指针会先到达末尾（null），判定无环；若有环，快慢指针必然相遇（快指针在环内追上慢指针）。相遇后，把一个指针移回 head，另一个留在相遇点，两者同速前进，再次相遇的位置即环入口。正确性：设头到入口距离 a、入口到相遇点距离 b、环长 L，则相遇时慢指针走 a+b，快指针走 2(a+b)，于是 a+b = kL，所以从相遇点走 a 步回到入口，与从 head 出发走 a 步的指针在入口相遇。全程 O(1) 空间。

解析

快指针是慢指针速度的两倍，环内相对速度为一个节点/步，故必然追上。环入口定位的关键是 a+b=kL（a 为头到环入口距离、b 为入口到第一次相遇点距离、L 为环长）：相遇后把快指针移回 head、慢指针留在相遇点，两者同速前进，慢指针再走 a 步（即总共 b+a=kL 步，模 L 为 0）回到环入口，与从 head 出发走 a 步的指针在环入口相遇。该算法无需额外存储，空间 O(1)。

示例代码

public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next; fast = fast.next.next;
        if (slow == fast) {
            ListNode p = head;
            while (p != slow) { p = p.next; slow = slow.next; }
            return p;
        }
    }
    return null;
}

#

★

17. 用两个队列实现栈，每次入队后把前面所有元素重新排队，使新元素位于队首

问题

说明如何用两个队列实现栈，描述每次入队后把前面所有元素重新排队使新元素位于队首的操作，并分析复杂度？

考察点

两个队列的角色切换
入队时把前面的元素移到另一个队列
O(1) 出栈与 O(n) 入栈

答案

维护两个队列 q1、q2，其中 q1 始终存放栈元素（栈顶在 q1 队首）。入栈时，把新元素先放入空的 q2，再把 q1 中所有元素依次移入 q2，然后交换 q1、q2 引用，使新元素成为 q1 队首（即栈顶）。出栈直接弹出 q1 队首，O(1)。入栈 O(n)，因为每入栈一个元素要移动当前所有元素。

解析

该实现把"新元素压入栈顶"体现为"新元素到队首"，通过把旧元素整体移到另一队列实现。也可以用相反策略（入栈 O(1)、出栈 O(n)），两种策略复杂度互补，取决于具体场景。

示例代码

class MyStack {
    Queue<Integer> q1 = new LinkedList<>(), q2 = new LinkedList<>();
    public void push(int x) {
        q2.offer(x);
        while (!q1.isEmpty()) q2.offer(q1.poll());
        Queue<Integer> t = q1; q1 = q2; q2 = t;
    }
    public int pop() { return q1.poll(); }
    public int top() { return q1.peek(); }
    public boolean empty() { return q1.isEmpty(); }
}

#

★

18. 设计一个支持 getMin 的栈，辅助栈与差值法两种实现的空间复杂度对比？

问题

说明如何设计一个支持 getMin 的栈，比较辅助栈与差值法两种实现的空间复杂度？

考察点

辅助栈同步记录最小值
差值法（编码差值）的实现
两种方法的空间复杂度对比

答案

辅助栈法：维护一个 minStack，每次入栈时把当前最小值压入 minStack，出栈时同步弹出，getMin 返回 minStack 栈顶。空间 O(n)（同步实现下最坏恒为 O(n)，如全递减序列时每个最小值都不同；优化版“仅新最小值时压入”最坏同样发生在全递减时）；差值法：只用一个栈，存当前元素与当前最小值的差值（或对最小值做编码），入栈时若新值更小则更新 min，出栈时通过差值还原上一个最小值。差值法空间上仍为 O(n)（每个元素一个存储单元），但省去了辅助栈，常数减半；不过差值法在元素值可能溢出或需要大数时需谨慎。

解析

两种方法空间渐进复杂度都是 O(n)，差值法在常数上更省（少一个栈），但实现更复杂且可能有溢出边界。工程上辅助栈更直观、更不易出错，最坏情况下两者空间相同（因为辅助栈中最小值可能每步都不同）。