算法系列-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;}