Java算法面试20题精解：排序、二叉树与链表实战

1. 面试算法题解析与实战指南

作为一名经历过上百场技术面试的Java开发者，我深知算法和数据结构在面试中的重要性。本文将深入解析20道经典的Java算法面试题，涵盖排序、二叉树、链表、栈队列等核心知识点。每道题我都会提供详细的解题思路、代码实现以及常见陷阱分析，帮助大家从零基础到精通掌握面试必备算法技能。

2. 数组与字符串处理

2.1 数组拼接最小数字问题

问题描述：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

解题思路：

1. 这个问题本质上是自定义排序问题
2. 我们需要定义一种比较规则：对于两个数字a和b，如果ab < ba，则认为a应该排在b前面
3. 使用Java的Collections.sort()方法配合自定义Comparator实现

代码实现：

import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; public class MinNumberCombination { public String printMinNumber(int[] numbers) { ArrayList<String> list = new ArrayList<>(); for (int num : numbers) { list.add(String.valueOf(num)); } Collections.sort(list, new Comparator<String>() { @Override public int compare(String a, String b) { String order1 = a + b; String order2 = b + a; return order1.compareTo(order2); } }); StringBuilder result = new StringBuilder(); for (String str : list) { result.append(str); } return result.toString(); } }

注意事项：

1. 注意处理数组为空或长度为0的特殊情况
2. 大数问题：当数组长度很大时，直接拼接字符串比较可能会超出整数范围，所以使用字符串比较更安全
3. 时间复杂度：O(nlogn)，主要来自排序操作

2.2 最大子数组和问题

问题描述：计算连续子向量的最大和，当向量全为正数的时候问题很好解决。但是，如果向量中包含负数，是否应该包含某个负数，并期望旁边的正数会弥补它呢？例如：{6,-3,-2,7,-15,1,2,2}，连续子向量的最大和为8(从第0个开始，到第3个为止)。

解题思路（Kadane算法）：

1. 维护两个变量：当前子数组和、最大子数组和
2. 遍历数组，对于每个元素：
   • 如果当前子数组和为负，则重置为当前元素值
   • 否则，将当前元素加入子数组和
   • 更新最大子数组和

代码实现：

public class MaxSubarray { public int findGreatestSum(int[] array) { if (array == null || array.length == 0) return 0; int currentSum = array[0]; int maxSum = array[0]; for (int i = 1; i < array.length; i++) { currentSum = Math.max(array[i], currentSum + array[i]); maxSum = Math.max(maxSum, currentSum); } return maxSum; } }

常见问题：

1. 全负数数组：算法仍然有效，会返回最大的那个负数
2. 空数组处理：需要特别判断，返回0或抛出异常视需求而定
3. 如果需要知道子数组的起止位置，可以扩展算法记录索引

3. 二叉树相关问题

3.1 重建二叉树

问题描述：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

解题思路：

1. 前序遍历的第一个元素是根节点
2. 在中序遍历中找到根节点，左边是左子树，右边是右子树
3. 递归构建左右子树

代码实现：

public class RebuildBinaryTree { public TreeNode buildTree(int[] preorder, int[] inorder) { return helper(0, 0, inorder.length - 1, preorder, inorder); } private TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) { if (preStart > preorder.length - 1 || inStart > inEnd) { return null; } TreeNode root = new TreeNode(preorder[preStart]); int inIndex = 0; // Index of current root in inorder for (int i = inStart; i <= inEnd; i++) { if (inorder[i] == root.val) { inIndex = i; break; } } root.left = helper(preStart + 1, inStart, inIndex - 1, preorder, inorder); root.right = helper(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, preorder, inorder); return root; } }

注意事项：

1. 假设输入数据有效（无重复元素，且能构成二叉树）
2. 时间复杂度：O(n)，每个节点都会被访问一次
3. 空间复杂度：O(n)，递归调用栈的深度

3.2 二叉搜索树的第k大节点

问题描述：给定一颗二叉搜索树，请找出其中的第k大的结点。

解题思路：

1. 二叉搜索树的中序遍历是升序序列
2. 中序遍历的倒序就是降序序列，可以方便地找到第k大元素
3. 使用递归或迭代方式实现中序遍历

代码实现：

public class KthLargestInBST { private int count = 0; private int result = 0; public int kthLargest(TreeNode root, int k) { this.count = k; reverseInorder(root); return result; } private void reverseInorder(TreeNode node) { if (node == null || count == 0) return; reverseInorder(node.right); if (--count == 0) { result = node.val; return; } reverseInorder(node.left); } }

优化技巧：

1. 提前终止：找到第k大元素后立即停止遍历
2. 迭代实现可以避免递归栈溢出的风险
3. 对于频繁查询的场景，可以为每个节点维护子树节点数量

4. 链表相关问题

4.1 反转链表

问题描述：输入一个链表，反转链表后，输出链表的所有元素。

解题思路：

1. 迭代法：使用三个指针(pre, cur, next)逐步反转
2. 递归法：递归到链表末端，然后逐层反转

迭代实现：

public class ReverseLinkedList { public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode nextTemp = curr.next; curr.next = prev; prev = curr; curr = nextTemp; } return prev; } }

递归实现：

public ListNode reverseListRecursive(ListNode head) { if (head == null || head.next == null) return head; ListNode p = reverseListRecursive(head.next); head.next.next = head; head.next = null; return p; }

性能比较：

1. 迭代法：O(n)时间，O(1)空间
2. 递归法：O(n)时间，O(n)空间（栈空间）

4.2 链表中倒数第k个节点

问题描述：输入一个链表，输出该链表中倒数第k个结点。

解题思路（快慢指针法）：

1. 快指针先走k步
2. 然后快慢指针一起走，当快指针到达末尾时，慢指针就是倒数第k个节点

代码实现：

public class KthFromEnd { public ListNode findKthToTail(ListNode head, int k) { if (head == null || k <= 0) return null; ListNode fast = head; ListNode slow = head; for (int i = 0; i < k; i++) { if (fast == null) return null; // k大于链表长度 fast = fast.next; } while (fast != null) { fast = fast.next; slow = slow.next; } return slow; } }

边界条件：

1. 链表为空
2. k为0或负数
3. k大于链表长度

5. 栈与队列问题

5.1 用两个栈实现队列

问题描述：用两个栈来实现一个队列，完成队列的Push和Pop操作。

解题思路：

1. 入队操作：直接压入栈A
2. 出队操作：如果栈B为空，将栈A的所有元素弹出并压入栈B，然后弹出栈B的栈顶

代码实现：

import java.util.Stack; public class QueueWithTwoStacks { private Stack<Integer> stack1 = new Stack<>(); private Stack<Integer> stack2 = new Stack<>(); public void push(int node) { stack1.push(node); } public int pop() { if (stack2.isEmpty()) { while (!stack1.isEmpty()) { stack2.push(stack1.pop()); } } return stack2.pop(); } }

复杂度分析：

1. 入队：O(1)
2. 出队：摊还时间复杂度O(1)（每个元素最多被压入和弹出各两次）

5.2 栈的排序

问题描述：按升序对栈进行排序（最大元素位于栈顶），要求最多只能使用一个额外的栈存放临时数据。

解题思路：

1. 使用辅助栈作为已排序部分
2. 从原栈弹出元素，与辅助栈栈顶比较，保持辅助栈从栈底到栈顶递减

代码实现：

import java.util.Stack; public class StackSorter { public static void sortStack(Stack<Integer> stack) { Stack<Integer> tempStack = new Stack<>(); while (!stack.isEmpty()) { int temp = stack.pop(); while (!tempStack.isEmpty() && tempStack.peek() > temp) { stack.push(tempStack.pop()); } tempStack.push(temp); } // 将元素从tempStack移回stack while (!tempStack.isEmpty()) { stack.push(tempStack.pop()); } } }

注意事项：

1. 只能使用栈的标准操作：push、pop、peek、isEmpty
2. 时间复杂度：O(n²)
3. 空间复杂度：O(n)（额外使用一个栈）

6. 数学与位运算问题

6.1 阶乘尾随零问题

问题描述：计算n的阶乘有多少个尾随零。

解题思路：

1. 尾随零由因子10产生，10=2×5
2. 在阶乘中，2的因子比5多，所以零的个数等于5的因子个数
3. 计算从1到n中所有数字包含的5的因子总数

代码实现：

public class TrailingZeros { public int countTrailingZeros(int n) { int count = 0; while (n > 0) { n /= 5; count += n; } return count; } }

优化分析：

1. 时间复杂度：O(logn)，因为每次n都除以5
2. 不需要计算完整的阶乘，避免大数问题

6.2 素因子只有3、5、7的第k个数

问题描述：设计一个算法，找出素因子只有3、5、7的第k个数。

解题思路（动态规划）：

1. 使用三个指针分别跟踪下一个应该乘以3、5、7的数
2. 每次选择三个乘积中的最小值作为下一个数
3. 更新对应指针

代码实现：

public class KthMagicNumber { public int getKthMagicNumber(int k) { if (k <= 0) return 0; int[] dp = new int[k]; dp[0] = 1; int p3 = 0, p5 = 0, p7 = 0; for (int i = 1; i < k; i++) { int next = Math.min(dp[p3] * 3, Math.min(dp[p5] * 5, dp[p7] * 7)); dp[i] = next; if (next == dp[p3] * 3) p3++; if (next == dp[p5] * 5) p5++; if (next == dp[p7] * 7) p7++; } return dp[k - 1]; } }

复杂度分析：

1. 时间复杂度：O(n)
2. 空间复杂度：O(n)

7. 高级数据结构问题

7.1 检查二叉树是否平衡

问题描述：实现一个函数，检查二叉树是否平衡，平衡的定义如下，对于树中的任意一个结点，其两颗子树的高度差不超过1。

解题思路：

1. 递归计算每个节点的左右子树高度
2. 检查高度差是否超过1
3. 优化：在计算高度的同时检查平衡性，避免重复计算

代码实现：

public class BalancedBinaryTree { public boolean isBalanced(TreeNode root) { return checkHeight(root) != -1; } private int checkHeight(TreeNode node) { if (node == null) return 0; int leftHeight = checkHeight(node.left); if (leftHeight == -1) return -1; int rightHeight = checkHeight(node.right); if (rightHeight == -1) return -1; if (Math.abs(leftHeight - rightHeight) > 1) { return -1; } return Math.max(leftHeight, rightHeight) + 1; } }

优化点：

1. 时间复杂度：O(n)，每个节点只访问一次
2. 空间复杂度：O(h)，递归栈深度为树高

7.2 二叉查找树验证

问题描述：实现一个函数，检查一棵二叉树是否为二叉查找树。

解题思路：

1. 二叉查找树定义：左子树所有节点小于根节点，右子树所有节点大于根节点
2. 中序遍历应为升序序列
3. 递归检查每个节点是否在合法范围内

代码实现：

public class BSTValidator { public boolean isValidBST(TreeNode root) { return validate(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean validate(TreeNode node, long min, long max) { if (node == null) return true; if (node.val <= min || node.val >= max) { return false; } return validate(node.left, min, node.val) && validate(node.right, node.val, max); } }

注意事项：

1. 使用Long类型避免整数边界值问题
2. 也可以使用中序遍历验证序列是否升序

8. 面试技巧与总结

8.1 算法面试准备策略

1. 分类练习：将算法题按数据结构分类（数组、字符串、链表、树等），每类集中练习
2. 模板记忆：掌握常见算法模板（DFS、BFS、二分查找、动态规划等）
3. 白板编程：练习在白板或纸上写代码，注意格式和边界条件
4. 复杂度分析：对每个解法都能准确分析时间和空间复杂度
5. 测试用例：设计各种边界测试用例验证代码正确性

8.2 面试中的常见错误

1. 不沟通思路：直接写代码而不解释思考过程
2. 忽略边界条件：没有考虑空输入、极端值等情况
3. 过早优化：一开始就追求最优解而忽略基本解法
4. 不测试代码：写完代码后不通过示例验证
5. 时间管理不当：在简单问题上花费太多时间

8.3 推荐学习资源

1. 书籍：
   • 《剑指Offer》
   • 《算法导论》
   • 《编程珠玑》
2. 在线平台：
   • LeetCode
   • 牛客网
   • HackerRank
3. 视频课程：
   • 算法与数据结构基础课程
   • 系统设计面试指南

在实际面试中，除了写出正确的代码外，清晰的沟通、良好的代码风格和全面的测试同样重要。建议在平时练习中就养成这些好习惯，这样在面试时才能自然展现。