# 链表的中间节点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

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

示例 1：

输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。

示例 2：

输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

提示：

• 链表的结点数范围是 [1, 100]
• 1 <= Node.val <= 100

# 方法 1：快慢指针

如果说我现在有链表如下，是奇数个。那么中间的节点就是 3

p2
p1
1	2	3	4	5	null

还有下面是偶数个的情况：

此时中间节点好像是 3，又好像是 4。但是题目要求是找靠右的 那么就是 4 了

p2
p1
1	2	3	4	5	6	null

此时让慢指针 p1 一次走一步，让快指针 p2 一次走 两步，下面是执行过程：

第一轮循环：p1 走一步，p2 走两步

		p2
	p1
1	2	3	4	5	null

没有走到头就重复该过程 p1 走一步，p2 走两步

				p2
		p1
1	2	3	4	5	null

此时 p2 的 next 为 nulll 了就停止，而现在 p1 所在的位置就是当前链表的中间节点了

这是奇数的情况，那偶数呢？

分析如下：

第一轮

		p2
	p1
1	2	3	4	5	6	null

第二轮

				p2
		p1
1	2	3	4	5	6	null

第三轮

						p2
			p1
1	2	3	4	5	6	null

此时 p2 本身就是 null 了就停止，而当前 p1 就是偶数个链表的中间节点了

总结：

• 每次 p1 一次走一步，p2 一次走两步。当 p2 的 next 或者 p2 的本身就是 null 时就停止移动，然后 p1 的当前位置就是中间节点

代码：

public ListNode middleNode(ListNode head) {

        ListNode p1 = head;

        ListNode p2 = head;

        while(p2 != null && p2.next != null)

        {

          p1 = p1.next;

          p2 = p2.next.next;

        }

        return p1;

    }