原文链接: https://wangwei.one/posts/jav…
前面，我们实现了 删除单链表倒数第 N 个节点 操作，本篇来聊聊，如何求一个链表的中间节点。
求链表的中间结点
Leetcode 876. Middle of the Linked List
给定一个非空的单链表，要求返回它的中间节点，如果中间节点有两个则返回第二个。
例如：
Input: [1,2,3,4,5]
Output: Node 3 from this list
Input: [1,2,3,4,5,6]
Output: Node 4 from this list
解法一
第一种解法的思路比较容易想得到，先计算出链表的总长度，再计算出中间节点的下标，然后得遍历得到对应的节点即可。
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {val = x;}
* }
*/
class Solution {
public ListNode middleNode(ListNode head) {
if(head == null){
return null;
}
int len = 0;
for(ListNode curr = head; curr != null;){
len++;
curr = curr.next;
}
int targetIndex = 0;
ListNode target = null;
for(ListNode curr = head; curr != null;){
if(targetIndex == len / 2){
target = curr;
break;
}
targetIndex++;
curr = curr.next;
}
return target;
}
}
解法二
第二种解法，使用快慢指针，让快指针的移动速度是慢指针的两倍，等到快指针到达终点时，慢指针恰好抵达中间节点。
一段小路上，A 车行驶的速度是 B 车的两倍，等到 A 车到达终点时，B 车恰好达到小路的中间位置。
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {val = x;}
* }
*/
class Solution {
public ListNode middleNode(ListNode head) {
if(head == null){
return null;
}
ListNode slow = head;
ListNode fast = head;
for(ListNode curr = slow; slow != null;){
if(fast == null || fast.next == null){
break;
}else{
fast = fast.next.next;
}
slow = slow.next;
}
return slow;
}
}
到目前为止，我们已经使用快慢指针解决三个单链表相关的问题了：
单链表环检测删除单链表倒数第 N 个节点
求链表的中间结点
解法三
解法三也比较巧妙，遍历单链表，只有当下标为奇数时，指针才向前移动，到最后，指针所指即为中间节点。
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {val = x;}
* }
*/
class Solution {
public ListNode middleNode(ListNode head) {
if(head == null){
return null;
}
ListNode target = head;
int index = 0;
for(ListNode curr = head; curr != null;){
if(index % 2 == 1){
target = target.next;
}
index++;
curr = curr.next;
}
return target;
}
}
以上三种解法的时间复杂度均为 O(n)，在 leetcode 上的运行时间为 1ms，超过 82.96%。
相关练习
链表反转
链表环检测
有序链表合并
删除倒数第 N 个节点
参考资料
《数据结构与算法之美》