链表
/反转链表 迭代 ListNode reverseList(ListNode head) { ListNode prev = null, cur = head; while (cur != null) { ListNode next = cur.next; // 1. 先存下一个，防断链 cur.next = prev; // 2. 反转当前指针 prev = cur; // 3. prev 前进 cur = next; // 4. cur 前进 } return prev; // prev 是新头 } 递归 ListNode reverseList(ListNode head) { if (head == null || head.next == null) return head; ListNode newHead = reverseList(head.next); // 先反转后面 head.next.next = head; // 让后一个节点指回自己 head.next = null; // 断开原方向，防成环 return newHead; } /快慢指针 ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } boolean hasCycle(ListNode head) { ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) return true; // 相遇 } return false; } 虚拟dummy ListNode dummy = new ListNode(0); dummy.next = head; ListNode cur = dummy; // ... 操作 ... return dummy.next; // 真正的头可能被改，返回 dummy.next
二叉树DFS
/二叉树递归骨架 // 104 最大深度：分解型，f(node) = max(f(left), f(right)) + 1 int maxDepth(TreeNode root) { if (root == null) return 0; return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; } // 226 翻转二叉树：遍历型，交换左右子树后递归 TreeNode invertTree(TreeNode root) { if (root == null) return null; TreeNode left = invertTree(root.left); // 先递归翻转 root.left = invertTree(root.right); root.right = left; return root; } /直径与 LCA // 543 直径：后序，每个节点算「左深+右深」更新全局最大，返回自身深度 int ans = 0; int diameter(TreeNode root) { if (root == null) return 0; int l = diameter(root.left), r = diameter(root.right); ans = Math.max(ans, l + r); // 经过该节点的最长路径 return Math.max(l, r) + 1; // 向上返回深度 } // 236 最近公共祖先：后序，左右各找到一个目标则当前节点即 LCA TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null || root == p || root == q) return root; TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); if (left != null && right != null) return root; // p、q 分居两侧 return left != null ? left : right; // 都在同一侧 }
回溯
/回溯通用框架 List<List<Integer>> res = new ArrayList<>(); void backtrack(int[] nums, List<Integer> path, boolean[] used) { if (path.size() == nums.length) { // 结束条件：选满了 res.add(new ArrayList<>(path)); // 注意：必须 new 一份拷贝 return; } for (int i = 0; i < nums.length; i++) { // 遍历选择列表 if (used[i]) continue; // 跳过已选 path.add(nums[i]); used[i] = true; // 【做选择】 backtrack(nums, path, used); // 递归下一层 path.remove(path.size() - 1); used[i] = false; // 【撤销选择】 } } /排列 / 组合/子集 // 组合/子集：用 start 控制起点，避免重复选（顺序无关） void backtrack(int[] nums, int start, List<Integer> path) { res.add(new ArrayList<>(path)); // 子集：每个节点都是答案 for (int i = start; i < nums.length; i++) { path.add(nums[i]); backtrack(nums, i + 1, path); // 传 i+1，不回头 path.remove(path.size() - 1); } } /含重复元素去重 Arrays.sort(nums); // 先排序，让相同元素相邻 void backtrack(int[] nums, int start, boolean[] used, List<Integer> path) { // ...收集答案... for (int i = start; i < nums.length; i++) { // 同一层里，跳过重复元素（前一个相同值没被用，说明同层已处理过） if (i > start && nums[i] == nums[i-1]) continue; if (used[i]) continue; // 做选择 / 递归 / 撤销 } }
