16.合并两个排序链表
题目描述：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
思路：
法1：递归实现，注意递归终止条件和单层递归逻辑。
- 单层逻辑，比较节点值大小，最小值链接下一层递归的最小值；
- 终止条件：节点为null，返回另一条链表的节点。
技巧：递归函数最重要的是明白功能（返回两个链表的较小值），其次是功能实现等。
法2：迭代实现，虚拟节点dummy，初始化cur指向新链表的头dummy。
- l1.val <= l2.val，l1指向的节点链接到cur.next，l1指向下一个节点
- 否则，l2指向的节点链接到cur.next，l2指向下一个节点。
- 重复上述两个过程，直到一个单链表为null
- 剩下的链接到cur后边
技巧：一般创建单链表，都会设置有一个虚拟节点，也叫哨兵，这样每个节点都有一个前驱结点。
代码：
public class Solution { // 法1.递归实现 public ListNode Merge(ListNode list1,ListNode list2) { if (list1 == null) return list2; if (list2 == null) return list1; if (list1.val <= list2.val) { list1.next = Merge(list1.next, list2); return list1; } else { list2.next = Merge(list1, list2.next); return list2; } } //法2：迭代实现 public ListNode Merge(ListNode list1,ListNode list2) { ListNode dummy = new ListNode(-1); ListNode cur = dummy; while (list1 != null && list2 != null) { if (list1.val <= list2.val) { cur.next = list1; list1 = list1.next; } else { cur.next = list2; list2 = list2.next; } cur = cur.next; } cur.next = list1 != null ? list1 : list2; return dummy.next; } }
17.树的子结构
题目描述：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
思路：树问题先考虑递归，这里使用两层递归。
- 外层递归：遍历大树，当前两头结点进内层递归，外层继续递归大树的左右子节点；
- 内层递归：传入两棵树当前头结点，依次比较（核心逻辑：结构和节点值比较）。
代码：
public class Solution { // 外层递归：依次遍历大树的每个节点与小树比较 public boolean HasSubtree(TreeNode root1,TreeNode root2) { if (root1 == null || root2 == null) return false; return judge(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2); } // 内层递归，进行结构和节点值的判断 public boolean judge(TreeNode root1, TreeNode root2) { if (root2 == null) return true; if (root1 == null) return false; if (root1.val != root2.val) return false; return judge(root1.left, root2.left) && judge(root1.right, root2.right); } }
18.二叉树的镜像
题目描述：操作给定的二叉树，将其变换为源二叉树的镜像。
比如： 源二叉树 8 / \ 6 10 / \ / \ 5 7 9 11 镜像二叉树 8 / \ 10 6 / \ / \ 11 9 7 5
思路：递归实现，递归函数：实现二叉树的镜像，先检查root节点，然后递归镜像左右子树。
- 终止条件：节点值为null返回；
- 递归逻辑：左右子节点互换；
注意点：先记录一下其中一个节点，防止递归另一个节点被改变（这里记右节点）。
代码：
public class Solution { // 递归实现 public TreeNode Mirror (TreeNode pRoot) { if (pRoot == null) return null; TreeNode tmp = pRoot.right; pRoot.right = Mirror(pRoot.left); pRoot.left = Mirror(tmp); return pRoot; } }
19.顺时针打印矩阵
题目描述：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
思路：官方提供的转圈打印：不断缩小矩阵的范围，我们可以使用矩阵的左上角和右下角唯一表示一个矩阵。设左上角坐标为(lx, ly), 右下角坐标为(rx, ry)，缩小一圈就是lx+1, ly+1, rx-1, ry-1。
代码：
public class Solution { ArrayList<Integer> ans = new ArrayList<>(); public ArrayList<Integer> printMatrix(int [][] matrix) { int row = matrix.length, col = matrix[0].length; if (matrix == null || row == 0 || col == 0) return ans; int lx = 0, ly = 0; int rx = row - 1, ry = col - 1; // 遍历矩阵的每一圈 while (lx <= rx && ly <= ry) { print(matrix, lx++, ly++, rx--, ry--); } return ans; } // 转圈打印,参数：该圈的标识位置（左上角和右下角坐标） public void print(int[][] matrix, int lx, int ly, int rx, int ry) { for (int j = ly; j <= ry; ++j) { ans.add(matrix[lx][j]); } for (int i = lx + 1; i <= rx; ++i) { ans.add(matrix[i][ry]); } int h = rx - lx + 1; // 若只有一行或者一列可以直接跳过第3、4边 if (h > 1) { for (int rj = ry - 1; rj >= ly; --rj) { ans.add(matrix[rx][rj]); } } int w = ry - ly + 1; if (w > 1) { for (int ri = rx - 1; ri >= lx + 1; --ri) { ans.add(matrix[ri][ly]); } } } }
20.实现最小栈
题目描述：定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
思路：栈结构的push和pop操作时间复杂度都是O(1)，但是返回最小值需要遍历整个栈，时间复杂度O(n)。若使用一个变量min来记录最小值，那么在栈进行pop操作时候，如何更新min值就比较麻烦。
解决此问题我们可以使用空间换时间，定义两个栈，辅助栈用来记录当前操作（加入新元素后）的最小值（最小栈）。两个栈同时进行压栈操作，但是最小栈在进行压栈操作时需要判断压入的数值大小：
- 若当前值>最小栈栈顶元素，压入最小栈栈顶元素；
- 若当前值<=最小栈栈顶元素，压入当前值。
代码：
public class Solution { Stack<Integer> normal = new Stack<>(); Stack<Integer> minval = new Stack<>(); public void push(int node) { normal.push(node); if (minval.isEmpty()) { minval.push(node); } else { if (node <= minval.peek()) { minval.push(node); } else { minval.push(minval.peek()); } } } public void pop() { normal.pop(); minval.pop(); } // 最小栈栈顶元素 public int top() { return minval.peek(); } public int min() { return minval.peek(); } }
