算法题 链表的中间结点

链表的中间结点

问题描述

给定一个非空单链表的头结点head，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

链表节点定义：

classListNode{intval;ListNodenext;ListNode(){}ListNode(intval){this.val=val;}ListNode(intval,ListNodenext){this.val=val;this.next=next;}}

示例：

输入:[1,2,3,4,5]输出:[3,4,5]解释:中间结点是值为3的结点 输入:[1,2,3,4,5,6]输出:[4,5,6]解释:有两个中间结点，值分别为3和4，返回第二个（值为4的结点）

算法思路

快慢指针：

1. 核心思想：

   • 使用两个指针：slow（慢指针）和fast（快指针）
   • slow每次移动 1 步，fast每次移动 2 步
   • 当fast到达链表末尾时，slow正好在中间位置

2. 关键：

   • 对于奇数长度：slow在第 (n+1)/2 个位置（真正的中间）
   • 对于偶数长度：slow在第 n/2 + 1 个位置（第二个中间结点）

3. 终止条件：

   • fast == null：链表长度为偶数
   • fast.next == null：链表长度为奇数
   • 循环条件：fast != null && fast.next != null

代码实现

方法一：快慢指针

/** * Definition for singly-linked list. */classListNode{intval;ListNodenext;ListNode(){}ListNode(intval){this.val=val;}ListNode(intval,ListNodenext){this.val=val;this.next=next;}}classSolution{/** * 找到链表的中间结点（如果有两个中间结点，返回第二个） * * @param head 链表头结点 * @return 中间结点 * * 算法思路（快慢指针）： * 1. slow每次移动1步，fast每次移动2步 * 2. 当fast到达末尾时，slow正好在中间 * 3. 处理奇偶长度的统一逻辑 */publicListNodemiddleNode(ListNodehead){// 初始化快慢指针ListNodeslow=head;ListNodefast=head;// 快指针每次走2步，慢指针每次走1步// 当快指针到达末尾时，慢指针就在中间while(fast!=null&&fast.next!=null){slow=slow.next;// 慢指针走1步fast=fast.next.next;// 快指针走2步}returnslow;}}

方法二：两次遍历

classSolution{/** * 两次遍历： * 1. 第一次遍历计算链表长度 * 2. 第二次遍历找到中间位置 */publicListNodemiddleNode(ListNodehead){// 第一次遍历：计算链表长度intlength=0;ListNodecurrent=head;while(current!=null){length++;current=current.next;}// 计算中间位置（第二个中间结点）intmiddle=length/2;// 第二次遍历：找到中间结点current=head;for(inti=0;i<middle;i++){current=current.next;}returncurrent;}}

方法三：数组存储

classSolution{/** * 使用数组存储所有结点，然后直接返回中间位置的结点 */publicListNodemiddleNode(ListNodehead){List<ListNode>nodes=newArrayList<>();ListNodecurrent=head;// 将所有结点存储到数组中while(current!=null){nodes.add(current);current=current.next;}// 返回中间结点returnnodes.get(nodes.size()/2);}}

算法分析

• 时间复杂度：

  • 快慢指针：O(n)
    • 只需要一次遍历，快指针走 n 步，慢指针走 n/2 步
  • 两次遍历：O(n)
    • 第一次遍历 n 步，第二次遍历 n/2 步，总计 1.5n 步
  • 数组存储：O(n)
    • 一次遍历存储，然后 O(1) 访问

• 空间复杂度：

  • 快慢指针：O(1)
    • 只使用两个指针变量
  • 两次遍历：O(1)
    • 只使用常数额外空间
  • 数组存储：O(n)
    • 需要存储所有结点的引用

算法过程

1：奇数长度链表 [1,2,3,4,5]

快慢指针：

初始: slow=1, fast=1 第1次循环: - slow = slow.next = 2 - fast = fast.next.next = 3 - 状态: slow=2, fast=3 第2次循环: - slow = slow.next = 3 - fast = fast.next.next = 5 - 状态: slow=3, fast=5 第3次循环检查: - fast.next = null，循环终止 返回 slow = 3

2：偶数长度链表 [1,2,3,4,5,6]

快慢指针：

初始: slow=1, fast=1 第1次循环: - slow = 2, fast = 3 第2次循环: - slow = 3, fast = 5 第3次循环: - slow = 4, fast = null (5.next.next = null) 循环终止条件: fast == null 返回 slow = 4

测试用例

importjava.util.*;publicclassTest{// 创建链表publicstaticListNodecreateList(int[]values){if(values.length==0)returnnull;ListNodehead=newListNode(values[0]);ListNodecurrent=head;for(inti=1;i<values.length;i++){current.next=newListNode(values[i]);current=current.next;}returnhead;}// 将链表转换为数组（用于输出）publicstaticint[]listToArray(ListNodehead){List<Integer>values=newArrayList<>();ListNodecurrent=head;while(current!=null){values.add(current.val);current=current.next;}returnvalues.stream().mapToInt(i->i).toArray();}publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：奇数长度ListNodehead1=createList(newint[]{1,2,3,4,5});ListNoderesult1=solution.middleNode(head1);System.out.println("Test 1: "+Arrays.toString(listToArray(result1)));// [3,4,5]// 测试用例2：偶数长度ListNodehead2=createList(newint[]{1,2,3,4,5,6});ListNoderesult2=solution.middleNode(head2);System.out.println("Test 2: "+Arrays.toString(listToArray(result2)));// [4,5,6]// 测试用例3：单个结点ListNodehead3=createList(newint[]{1});ListNoderesult3=solution.middleNode(head3);System.out.println("Test 3: "+Arrays.toString(listToArray(result3)));// [1]// 测试用例4：两个结点ListNodehead4=createList(newint[]{1,2});ListNoderesult4=solution.middleNode(head4);System.out.println("Test 4: "+Arrays.toString(listToArray(result4)));// [2]// 测试用例5：三个结点ListNodehead5=createList(newint[]{1,2,3});ListNoderesult5=solution.middleNode(head5);System.out.println("Test 5: "+Arrays.toString(listToArray(result5)));// [2,3]// 测试用例6：四个结点ListNodehead6=createList(newint[]{1,2,3,4});ListNoderesult6=solution.middleNode(head6);System.out.println("Test 6: "+Arrays.toString(listToArray(result6)));// [3,4]// 测试用例7：大链表int[]largeArray=newint[1000];for(inti=0;i<1000;i++){largeArray[i]=i+1;}ListNodehead7=createList(largeArray);ListNoderesult7=solution.middleNode(head7);System.out.println("Test 7: "+result7.val);// 501 (1000/2 + 1 = 501)// 测试用例8：边界值ListNodehead8=createList(newint[]{100000});ListNoderesult8=solution.middleNode(head8);System.out.println("Test 8: "+Arrays.toString(listToArray(result8)));// [100000]}}

关键点

1. 快慢指针：

   • 慢指针：每次1步
   • 快指针：每次2步

2. 循环终止条件：

   • fast != null && fast.next != null
   • 确保快指针可以安全地移动2步

3. 奇偶长度统一处理：

   • 偶数长度时返回第二个中间结点

常见问题

1. 为什么快指针要检查 fast.next != null？

   • 快指针每次要移动2步：fast.next.next
   • 如果fast.next == null，那么fast.next.next会抛出 NullPointerException

2. 快慢指针的其他应用？

   • 检测链表是否有环（Floyd判圈算法）
   • 找到链表的倒数第k个结点
   • 分割链表为两半