解题思路：
栈无法实现队列功能： 栈底元素（对应队首元素）无法直接删除，需要将上方所有元素出栈。
双栈可实现列表倒序： 设有含三个元素的栈 A = [1,2,3]A=[1,2,3] 和空栈 B = []B=[]。若循环执行 AA 元素出栈并添加入栈 BB ，直到栈 AA 为空，则 A = []A=[] , B = [3,2,1]B=[3,2,1] ，即 栈 BB 元素实现栈 AA 元素倒序 。
利用栈 BB 删除队首元素： 倒序后，BB 执行出栈则相当于删除了 AA 的栈底元素，即对应队首元素。
函数设计：
题目只要求实现 加入队尾appendTail() 和 删除队首deleteHead() 两个函数的正常工作，因此我们可以设计栈 A 用于加入队尾操作，栈 B 用于将元素倒序，从而实现删除队首元素。
加入队尾 appendTail()函数： 将数字 val 加入栈 A 即可。
删除队首deleteHead()函数： 有以下三种情况。
当栈 B 不为空： B中仍有已完成倒序的元素，因此直接返回 B 的栈顶元素。
否则，当 A 为空： 即两个栈都为空，无元素，因此返回 -1−1 。
否则： 将栈 A 元素全部转移至栈 B 中，实现元素倒序，并返回栈 B 的栈顶元素。
复杂度分析：
由于问题特殊，以下分析仅满足添加 N个元素并删除 N个元素，即栈初始和结束状态下都为空的情况。
时间复杂度： appendTail()函数为 O(1) ；deleteHead() 函数在 N 次队首元素删除操作中总共需完成 N 个元素的倒序。
空间复杂度 O(N) ： 最差情况下，栈 A 和 B 共保存 N 个元素。
class CQueue {
linkedList A, B;
public CQueue() {
A = new linkedList();
B = new linkedList();
}
public void appendTail(int value) {
A.addLast(value);
}
public int deleteHead() {
if(!B.isEmpty()) return B.removeLast();
if(A.isEmpty()) return -1;
while(!A.isEmpty())
B.addLast(A.removeLast());
return B.removeLast();
}
}
面试题30. 包含 min 函数的栈（辅助栈，清晰图解）
解题思路：
普通栈的 push() 和 pop() 函数的复杂度为 O(1)O(1) ；而获取栈最小值 min() 函数需要遍历整个栈，复杂度为 O(N)O(N) 。
本题难点： 将 min() 函数复杂度降为 O(1)O(1) ，可通过建立辅助栈实现；
数据栈 AA ： 栈 AA 用于存储所有元素，保证入栈 push() 函数、出栈 pop() 函数、获取栈顶 top() 函数的正常逻辑。
辅助栈 BB ： 栈 BB 中存储栈 AA 中所有 非严格降序 的元素，则栈 AA 中的最小元素始终对应栈 BB 的栈顶元素，即 min() 函数只需返回栈 BB 的栈顶元素即可。
因此，只需设法维护好 栈 BB 的元素，使其保持非严格降序，即可实现 min() 函数的 O(1)O(1) 复杂度。
函数设计：
push(x) 函数： 重点为保持栈 BB 的元素是 非严格降序 的。
将 xx 压入栈 AA （即 A.add(x) ）；
若 ① 栈 BB 为空 或 ② xx 小于等于 栈 BB 的栈顶元素，则将 xx 压入栈 BB （即 B.add(x) ）。
pop() 函数： 重点为保持栈 A, BA,B 的 元素一致性 。
执行栈 AA 出栈（即 A.pop() ），将出栈元素记为 yy ；
若 yy 等于栈 BB 的栈顶元素，则执行栈 B 出栈（即 B.pop() ）。
top() 函数： 直接返回栈 AA 的栈顶元素即可，即返回 A.peek() 。
min() 函数： 直接返回栈 BB 的栈顶元素即可，即返回 B.peek() 。
复杂度分析：
时间复杂度 O(1) ： push(), pop(), top(), min() 四个函数的时间复杂度均为常数级别。
空间复杂度 O(N)： 当共有 NN 个待入栈元素时，辅助栈 BB 最差情况下存储 NN 个元素，使用 O(N)O(N) 额外空间。
代码：
Java 代码中，由于 Stack 中存储的是 int 的包装类 Integer ，因此需要使用 equals() 代替 == 来比较值是否相等。
class MinStack {
Stack stack = new Stack<>();
Stack minStack = new Stack<>();
public MinStack() {
}
public void push(int x) {
stack.push(x);
if(minStack.isEmpty()||x<=minStack.peek()){
minStack.push(x);
}
}
public void pop() {
if(stack.isEmpty())
return;
if (Objects.equals(stack.peek(), minStack.peek()))
{
stack.pop();
minStack.pop();
}
else stack.pop();
}
public int top() {
return stack.peek();
}
public int min() {
return minStack.peek();
}
}
面试题06. 从尾到头打印链表（递归法、辅助栈法，清晰图解）
方法一：递归法
解题思路：
利用递归： 先走至链表末端，回溯时依次将节点值加入列表 ，这样就可以实现链表值的倒序输出。
Java 算法流程：
递推阶段： 每次传入 head.next ，以 head == null（即走过链表尾部节点）为递归终止条件，此时直接返回。
回溯阶段： 层层回溯时，将当前节点值加入列表，即tmp.add(head.val)。
最终，将列表 tmp 转化为数组 res ，并返回即可。
复杂度分析：
时间复杂度 O(N)： 遍历链表，递归 NN 次。
空间复杂度 O(N)： 系统递归需要使用 O(N)O(N) 的栈空间。
图解以 Python 代码为例， Java 原理一致，只是把利用返回值改为 add() 操作。
class Solution {
ArrayList tmp = new ArrayList();
public int[] reversePrint(ListNode head) {
recur(head);
int[] res = new int[tmp.size()];
for(int i = 0; i < res.length; i++)
res[i] = tmp.get(i);
return res;
}
void recur(ListNode head) {
if(head == null) return;
recur(head.next);
tmp.add(head.val);
}
}
方法二：辅助栈法
解题思路：
链表特点： 只能从前至后访问每个节点。
题目要求： 倒序输出节点值。
这种 先入后出 的需求可以借助 栈 来实现。
算法流程：
入栈： 遍历链表，将各节点值 push 入栈。（Python 使用 append() 方法，Java借助 linkedList 的addLast()方法）。
出栈： 将各节点值 pop 出栈，存储于数组并返回。（Python 直接返回 stack 的倒序列表，Java 新建一个数组，通过 popLast() 方法将各元素存入数组，实现倒序输出）。
复杂度分析：
时间复杂度 O(N)： 入栈和出栈共使用 O(N)O(N) 时间。
空间复杂度 O(N)： 辅助栈 stack 和数组 res 共使用 O(N)O(N) 的额外空间。
图解以 Java 代码为例，Python 无需将 stack 转移至 res，而是直接返回倒序数组。
class Solution {
public int[] reversePrint(ListNode head) {
linkedList stack = new linkedList();
while(head != null) {
stack.addLast(head.val);
head = head.next;
}
int[] res = new int[stack.size()];
for(int i = 0; i < res.length; i++)
res[i] = stack.removeLast();
return res;
}
}
剑指 Offer 24. 反转链表（迭代 / 递归，清晰图解）
解题思路：
如下图所示，题目要求将链表反转。本文介绍迭代（双指针）、递归两种实现方法。
方法一：迭代（双指针）
考虑遍历链表，并在访问各节点时修改 next 引用指向，算法流程见注释。
复杂度分析：
时间复杂度 O(N)： 遍历链表使用线性大小时间。
空间复杂度 O(1) ： 变量 pre 和 cur 使用常数大小额外空间。
class Solution {
public ListNode reverseList(ListNode head) {
ListNode cur = head, pre = null;
while(cur != null) {
ListNode tmp = cur.next; // 暂存后继节点 cur.next
cur.next = pre; // 修改 next 引用指向
pre = cur; // pre 暂存 cur
cur = tmp; // cur 访问下一节点
}
return pre;
}
}
方法二：递归
考虑使用递归法遍历链表，当越过尾节点后终止递归，在回溯时修改各节点的 next 引用指向。
recur(cur, pre) 递归函数：
终止条件：当 cur 为空，则返回尾节点 pre （即反转链表的头节点）；
递归后继节点，记录返回值（即反转链表的头节点）为 res ；
修改当前节点 cur 引用指向前驱节点 pre ；
返回反转链表的头节点 res ；
reverseList(head) 函数：
调用并返回 recur(head, null) 。传入 null 是因为反转链表后， head 节点指向 null ；
复杂度分析：
时间复杂度 O(N) ： 遍历链表使用线性大小时间。
空间复杂度 O(N) ： 遍历链表的递归深度达到 N，系统使用 O(N) 大小额外空间。
class Solution {
public ListNode reverseList(ListNode head) {
return recur(head, null); // 调用递归并返回
}
private ListNode recur(ListNode cur, ListNode pre) {
if (cur == null) return pre; // 终止条件
ListNode res = recur(cur.next, cur); // 递归后继节点
cur.next = pre; // 修改节点引用指向
return res; // 返回反转链表的头节点
}
}
剑指 Offer 35. 复杂链表的复制（哈希表 / 拼接与拆分，清晰图解）
普通链表的节点定义如下：
// Definition for a Node.
class Node {
int val;
Node next;
public Node(int val) {
this.val = val;
this.next = null;
}
}
本题链表的节点定义如下：
// Definition for a Node.
class Node {
int val;
Node next, random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
给定链表的头节点 head ，复制普通链表很简单，只需遍历链表，每轮建立新节点 + 构建前驱节点 pre 和当前节点 node 的引用指向即可。
本题链表的节点新增了 random 指针，指向链表中的 任意节点 或者 nullnull 。这个 random 指针意味着在复制过程中，除了构建前驱节点和当前节点的引用指向 pre.next ，还要构建前驱节点和其随机节点的引用指向 pre.random 。
本题难点： 在复制链表的过程中构建新链表各节点的 random 引用指向。
class Solution {
public Node copyRandomList(Node head) {
Node cur = head;
Node dum = new Node(0), pre = dum;
while(cur != null) {
Node node = new Node(cur.val); // 复制节点 cur
pre.next = node; // 新链表的 前驱节点 -> 当前节点
// pre.random = "???"; // 新链表的 「 前驱节点 -> 当前节点 」 无法确定
cur = cur.next; // 遍历下一节点
pre = node; // 保存当前新节点
}
return dum.next;
}
}
方法一：哈希表
利用哈希表的查询特点，考虑构建 原链表节点 和 新链表对应节点 的键值对映射关系，再遍历构建新链表各节点的 next 和 random 引用指向即可。
算法流程：
若头节点 head 为空节点，直接返回 null；
初始化： 哈希表 dic ， 节点 cur 指向头节点；
复制链表：
建立新节点，并向 dic 添加键值对 (原 cur 节点, 新 cur 节点） ；
cur 遍历至原链表下一节点；
构建新链表的引用指向：
构建新节点的 next 和 random 引用指向；
cur 遍历至原链表下一节点；
返回值： 新链表的头节点 dic[cur] ；
复杂度分析：
时间复杂度 O(N) ： 两轮遍历链表，使用 O(N)时间。
空间复杂度 O(N) ： 哈希表 dic 使用线性大小的额外空间。
class Solution {
public Node copyRandomList(Node head) {
if(head == null) return null;
Node cur = head;
Map map = new HashMap<>();
// 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
while(cur != null) {
map.put(cur, new Node(cur.val));
cur = cur.next;
}
cur = head;
// 4. 构建新链表的 next 和 random 指向
while(cur != null) {
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
// 5. 返回新链表的头节点
return map.get(head);
}
}
方法二：拼接 + 拆分
考虑构建 原节点 1 -> 新节点 1 -> 原节点 2 -> 新节点 2 -> …… 的拼接链表，如此便可在访问原节点的 random 指向节点的同时找到新对应新节点的 random 指向节点。
算法流程：
复制各节点，构建拼接链表:
设原链表为 node1 rightarrow node2 rightarrow cdotsnode1→node2→⋯ ，构建的拼接链表如下所示：
node1 rightarrow node1_{new} rightarrow node2 rightarrow node2_{new} rightarrow cdots
node1→node1
new
→node2→node2
new
→⋯
构建新链表各节点的 random 指向：
当访问原节点 cur 的随机指向节点 cur.random 时，对应新节点 cur.next 的随机指向节点为 cur.random.next 。
拆分原 / 新链表：
设置 pre / cur 分别指向原 / 新链表头节点，遍历执行 pre.next = pre.next.next 和 cur.next = cur.next.next 将两链表拆分开。
返回新链表的头节点 res 即可。
复杂度分析：
时间复杂度 O(N)： 三轮遍历链表，使用 O(N)时间。
空间复杂度 O(1)： 节点引用变量使用常数大小的额外空间。
class Solution {
public Node copyRandomList(Node head) {
if(head == null) return null;
Node cur = head;
// 1. 复制各节点，并构建拼接链表
while(cur != null) {
Node tmp = new Node(cur.val);
tmp.next = cur.next;
cur.next = tmp;
cur = tmp.next;
}
// 2. 构建各新节点的 random 指向
cur = head;
while(cur != null) {
if(cur.random != null)
cur.next.random = cur.random.next;
cur = cur.next.next;
}
// 3. 拆分两链表
cur = head.next;
Node pre = head, res = head.next;
while(cur.next != null) {
pre.next = pre.next.next;
cur.next = cur.next.next;
pre = pre.next;
cur = cur.next;
}
pre.next = null; // 单独处理原链表尾节点
return res; // 返回新链表头节点
}
}
面试题05. 替换空格 （字符串修改，清晰图解）
方法一：遍历添加
在 Python 和 Java 等语言中，字符串都被设计成「不可变」的类型，即无法直接修改字符串的某一位字符，需要新建一个字符串实现。
算法流程：
初始化一个 list (Python) / StringBuilder (Java) ，记为 res ；
遍历列表 s 中的每个字符 c ：
当 c 为空格时：向 res 后添加字符串 “%20” ；
当 c 不为空格时：向 res 后添加字符 c ；
将列表 res 转化为字符串并返回。
复杂度分析：
时间复杂度 O(N)O(N) ： 遍历使用 O(N)O(N) ，每轮添加（修改）字符操作使用 O(1)O(1) ；
空间复杂度 O(N)O(N) ： Python 新建的 list 和 Java 新建的 StringBuilder 都使用了线性大小的额外空间。
class Solution {
public String replaceSpace(String s) {
StringBuilder res = new StringBuilder();
for(Character c : s.toCharArray())
{
if(c == ' ') res.append("%20");
else res.append(c);
}
return res.toString();
}
}
时间复杂度 O(N)O(N) ： 遍历使用 O(N)O(N) ，每轮添加（修改）字符操作使用 O(1)O(1) ；
空间复杂度 O(N)O(N) ： Python 新建的 list 和 Java 新建的 StringBuilder 都使用了线性大小的额外空间。
class Solution {
public String replaceSpace(String s) {
StringBuilder res = new StringBuilder();
for(Character c : s.toCharArray())
{
if(c == ' ') res.append("%20");
else res.append(c);
}
return res.toString();
}
}
