Java刷题笔记（0923）：最长回文子串、合并有序数组与合并链表
学习日期：09 月 23 日
关键词：中心扩展、双指针、虚拟头节点、排序算法
本篇包含三道题，分别练习字符串中心扩展、数组尾部双指针和链表虚拟头节点，并在最后复习常用排序算法。
一、最长回文子串
题目链接：LeetCode 5. 最长回文子串
回文字符串从左向右和从右向左读取相同：
奇数长度：aba 偶数长度：abba1. 方法一：枚举子串并判断
枚举子串的左右边界，再使用双指针判断是否为回文。
classSolution{publicStringlongestPalindrome(Strings){intmaxLength=0;intstart=0;for(inti=0;i<s.length();i++){for(intj=i;j<s.length();j++){if(isPalindrome(s,i,j)&&j-i+1>maxLength){maxLength=j-i+1;start=i;}}}returns.substring(start,start+maxLength);}privatebooleanisPalindrome(Strings,intleft,intright){while(left<right){if(s.charAt(left)!=s.charAt(right)){returnfalse;}left++;right--;}returntrue;}}复杂度：
- 子串数量为
O(n²)； - 每次判断回文最坏为
O(n)； - 总时间复杂度为
O(n³)； - 空间复杂度为
O(1)。
该方法适合建立基本思路，但字符串稍长时效率较低。
2. 方法二：中心扩展
回文串一定围绕中心对称。以每个位置为中心向两侧扩展，并分别处理：
奇数回文中心：(i, i) 偶数回文中心：(i, i + 1)classSolution{publicStringlongestPalindrome(Strings){intstart=0;intmaxLength=0;for(inti=0;i<s.length();i++){intoddLength=expand(s,i,i);intevenLength=expand(s,i,i+1);intlength=Math.max(oddLength,evenLength);if(length>maxLength){maxLength=length;start=i-(length-1)/2;}}returns.substring(start,start+maxLength);}privateintexpand(Strings,intleft,intright){while(left>=0&&right<s.length()&&s.charAt(left)==s.charAt(right)){left--;right++;}returnright-left-1;}}为什么长度是：
right-left-1循环停止时，left和right已经分别多走了一步，所以真正的回文区间是：
[left + 1, right - 1]长度为：
(right - 1) - (left + 1) + 1 = right - left - 1复杂度：
- 时间复杂度：
O(n²)； - 空间复杂度：
O(1)。
3. 方法补充
这道题还可以使用：
- 动态规划：时间
O(n²)，空间O(n²)； - Manacher算法：时间
O(n)，但实现和理解成本更高。
面试和常规刷题中，中心扩展通常在代码复杂度和运行效率之间取得了较好的平衡。
二、合并两个有序数组
题目链接：LeetCode 88. 合并两个有序数组
nums1的长度为m+n，前m个位置保存有效元素，后面预留空间用于合并nums2。
1. 方法一：从尾部开始的三指针
这不是“边插边排”，更准确的名称是：逆向双指针合并。
如果从数组头部填充，可能覆盖nums1中尚未比较的元素；从尾部开始则不会产生覆盖问题。
classSolution{publicvoidmerge(int[]nums1,intm,int[]nums2,intn){intp1=m-1;intp2=n-1;intwrite=m+n-1;while(p2>=0){if(p1>=0&&nums1[p1]>nums2[p2]){nums1[write--]=nums1[p1--];}else{nums1[write--]=nums2[p2--];}}}}为什么只需要判断：
while(p2>=0)- 如果
nums2先处理完，nums1剩余元素本来就在正确位置； - 如果
nums1先处理完，继续把nums2剩余元素写入nums1即可。
复杂度：
- 时间复杂度：
O(m+n)； - 空间复杂度：
O(1)。
2. 方法二：先复制，再排序
classSolution{publicvoidmerge(int[]nums1,intm,int[]nums2,intn){for(inti=0;i<n;i++){nums1[m+i]=nums2[i];}Arrays.sort(nums1);}}复杂度：
- 复制：
O(n)； - 排序：
O((m+n)log(m+n))； - 总时间复杂度：
O((m+n)log(m+n))。
代码更短，但没有利用两个数组原本已经有序的条件。
三、合并两个有序链表
题目链接：LeetCode 21. 合并两个有序链表
1. 虚拟头节点
如果直接构造结果链表，需要单独处理“第一个节点是谁”。使用虚拟头节点dummy后，每一次追加节点都可以使用相同逻辑。
classSolution{publicListNodemergeTwoLists(ListNodelist1,ListNodelist2){ListNodedummy=newListNode(-1);ListNodetail=dummy;while(list1!=null&&list2!=null){if(list1.val<=list2.val){tail.next=list1;list1=list1.next;}else{tail.next=list2;list2=list2.next;}tail=tail.next;}tail.next=(list1!=null)?list1:list2;returndummy.next;}}这里要区分两个指针：
dummy：始终保存结果链表虚拟头部的位置 tail：不断向后移动，指向结果链表的最后一个节点原代码中：
ListNodedummy=newListNode();ListNoderes=newListNode();res=dummy;第二次创建的节点会立即被覆盖，没有实际作用。直接写成：
ListNodedummy=newListNode(-1);ListNodetail=dummy;即可。
复杂度：
- 时间复杂度：
O(m+n)； - 空间复杂度：
O(1)，复用了原链表节点。
四、数组合并与链表合并的共同思想
两道合并题都利用了输入已经有序这一条件：
比较两个候选元素 ↓ 选择更合适的一个放入结果 ↓ 移动对应指针区别在于：
| 场景 | 主要问题 | 解决方法 |
|---|---|---|
| 数组合并 | 从头写会覆盖有效元素 | 从尾部向前写 |
| 链表合并 | 第一个结果节点需要特殊处理 | 使用虚拟头节点 |
五、常用排序算法复习
1. 冒泡排序
相邻元素两两比较，把较大的元素逐轮移动到末尾。
publicstaticvoidbubbleSort(int[]nums){for(intend=nums.length-1;end>0;end--){booleanswapped=false;for(inti=0;i<end;i++){if(nums[i]>nums[i+1]){inttemp=nums[i];nums[i]=nums[i+1];nums[i+1]=temp;swapped=true;}}if(!swapped){break;}}}- 平均时间复杂度：
O(n²)； - 最好时间复杂度：优化后为
O(n)； - 空间复杂度：
O(1)； - 稳定排序。
2. 选择排序
每轮从未排序区域中选出最小元素，放到当前起始位置。
publicstaticvoidselectionSort(int[]nums){for(inti=0;i<nums.length-1;i++){intminIndex=i;for(intj=i+1;j<nums.length;j++){if(nums[j]<nums[minIndex]){minIndex=j;}}inttemp=nums[i];nums[i]=nums[minIndex];nums[minIndex]=temp;}}- 时间复杂度：
O(n²)； - 空间复杂度：
O(1)； - 通常不稳定。
3. 快速排序
选择一个基准值，将较小元素放在左侧、较大元素放在右侧，然后递归处理两部分。
publicstaticvoidquickSort(int[]nums,intleft,intright){if(left>=right){return;}intpivotIndex=partition(nums,left,right);quickSort(nums,left,pivotIndex-1);quickSort(nums,pivotIndex+1,right);}privatestaticintpartition(int[]nums,intleft,intright){intpivot=nums[right];intsmaller=left;for(inti=left;i<right;i++){if(nums[i]<=pivot){inttemp=nums[i];nums[i]=nums[smaller];nums[smaller]=temp;smaller++;}}inttemp=nums[smaller];nums[smaller]=nums[right];nums[right]=temp;returnsmaller;}- 平均时间复杂度：
O(n log n)； - 最坏时间复杂度：
O(n²)； - 递归栈平均为
O(log n)； - 通常不稳定。
实际使用时，可通过随机选择基准值降低持续遇到最坏情况的风险。
4. 桶排序
桶排序先按数值范围把元素分配到多个桶中，每个桶内部排序后再依次合并。
原数据 ↓ 按范围分桶 桶0：0～9 桶1：10～19 桶2：20～29 ↓ 桶内排序并合并 有序结果桶排序适合：
- 数据分布比较均匀；
- 能够合理划分数值范围；
- 额外空间可以接受。
在分布较均匀、桶数量设计合理时，平均性能可以接近O(n)；但如果所有元素都进入同一个桶，性能会退化为桶内排序算法的复杂度。
5. 排序对比
| 排序算法 | 平均时间 | 最坏时间 | 额外空间 | 稳定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 快速排序 | O(n log n) | O(n²) | 平均O(log n) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 |
| 桶排序 | 依赖数据分布 | 依赖桶内排序 | O(n+k) | 取决于实现 |
“稳定”指的是：两个值相等的元素经过排序后，原有的相对顺序是否保持不变。
六、复盘
今天的三道题分别对应三个值得复用的模板：
回文字符串 → 枚举中心并向两侧扩展 合并有序数组 → 从尾部写入，避免覆盖 合并有序链表 → dummy固定头部，tail负责移动做题时应该优先利用题目提供的条件。例如“两个数组已经有序”意味着不需要重新完整排序，“结果直接写入nums1”意味着需要思考如何避免覆盖原有数据。
