算法系列-力扣876-求链表的中间节点
# 求链表中间节点，如果有两个中间节点取后面那个
链表定义
```
// @lc code=start
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
```
方法一：计数取一半
解题方法：
先计算链表一共有多少个节点n
n/2,得到中间节点的下标（从0开始）
1 -> 2 -> 3 -> 4 -> 5
坐标节点就是链表的中间节点
时间复杂度：O(n)
空间复杂度：O(1)
```
public ListNode middleNode(ListNode head) {
/**
* 先计算链表一共有多少个节点n
* n/2,得到中间节点的下标（从0开始）
* 1 -> 2 -> 3 -> 4 -> 5
* 坐标节点就是链表的中间节点
* */
int n=0;
ListNode p=head;
while (p!=null){
n++;
p=p.next;
}
int mid=n/2;
ListNode midNode=head;
for (int i = 0; i < mid; i++) {
midNode=midNode.next;
}
return midNode;
}
```
方法二：双指针
解题方法：
定义快慢两个指针，快指针每次移动2步，慢指针每次移动1步
注意：指针需要从头节点前开始移动，因此需要定义一个哑结点，快指针和慢指针都从哑节点开始
当快指针移动了2k步后，慢指针移动了k步
假设2k=n，k=n/2
当n为偶数时，慢指针的后续节点就是中间节点
当n为奇数时，慢指针就是中间节点
是否是偶数节点看快指针每次是否都能移动两步
时间复杂度：O(n)
空间复杂度：O(1)
```
public ListNode middleNode(ListNode head) {
/**
* 定义快慢两个指针，快指针每次移动2步，慢指针每次移动1步
* 注意：指针需要从头节点前开始移动，因此需要定义一个哑结点，快指针和慢指针都从哑节点开始
* 当快指针移动了2k步后，慢指针移动了k步
* 假设2k=n，k=n/2
* 当n为偶数时，慢指针的后续节点就是中间节点
* 当n为奇数时，慢指针就是中间节点
* 是否是偶数节点看快指针每次是否都能移动两步
* -1 -> 1 -> 2 -> 3 -> 4 -> 5 -> null
* -1 -> 1 -> 2 -> 3 -> 4 -> null
* */
if(head == null){
return null;
}
ListNode dummy = new ListNode(-1);
dummy.next=head;
ListNode slow=dummy;
ListNode fast=dummy;
ListNode midNode=null;
Boolean isEvent=true;
while (fast.next!=null){
slow=slow.next;
if(fast.next.next!=null) {
fast = fast.next.next;
} else{
fast=fast.next;
isEvent=false;
}
}
midNode = isEvent ? slow.next : slow;
return midNode;
}
```
方法三：双指针优化
解题方法：
定义快慢两个指针，快指针每次移动2步，慢指针每次移动1步
快指针和慢指针都从头节点开始移动
当快指针移动到链尾时，慢指针移动了k步，n>1
当n为偶数时，n-1必然是奇数
即快指针移动了2(k-1)+1步
此时快慢指针距离原点距离
快2(k-1)+1+1 简化 2k
慢k+1
即慢指针正好处于链表中间位置。
当n为奇数时，n-1必然是偶数
，快指针移动了2k步
此时快慢指针距离原点距离
2k+1
k+1
即慢指针正好处于链表中间位置
时间复杂度：O(n)
空间复杂度：O(1)
方法二的本质是下面的公式：
偶数
快2k
慢k
中间k+1
奇数
快2k-1
慢k
中间k
即快慢指针的初始位置+1就把公式统一了。
```
public ListNode middleNode(ListNode head) {
if(head == null){
return null;
}
ListNode slow=head;
ListNode fast=head;
while (fast!=null && fast.next!=null){
slow=slow.next;
fast = fast.next.next;
}
return slow;
}
```