链表的中间结点（Java实现）
题目：给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：[1,2,3,4,5] 输出：此列表中的结点 3 (序列化形式：[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。 注意，我们返回了一个 ListNode 类型的对象 ans，这样： ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：
输入：[1,2,3,4,5,6] 输出：此列表中的结点 4 (序列化形式：[4,5,6]) 由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
提示：
给定链表的结点数介于 1 和 100 之间。
思路很简单，代码实现之：
package Day49; /** * @Author Zhongger * @Description 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。 * 如果有两个中间结点，则返回第二个中间结点。 * @Date 2020.3.23 */ public class MiddleNodeSolution { public static void main(String[] args) { ListNode head = new ListNode(0); ListNode node1 = new ListNode(1); ListNode node2 = new ListNode(2); ListNode node3 = new ListNode(3); ListNode node4 = new ListNode(4); ListNode node5 = new ListNode(5); head.next=node1; node1.next=node2; node2.next=node3; node3.next=node4; node4.next=node5; MiddleNodeSolution solution = new MiddleNodeSolution(); System.out.println(solution.middleNode(head).val); } public ListNode middleNode(ListNode head) { if (head==null){ return null; } ListNode preNode=head; int size=0; while (preNode!=null){ size++; preNode=preNode.next; } int middleIndex = size / 2;//中间节点在链表中的位置 preNode=head; for (int i = 0; i < middleIndex; i++) { preNode=preNode.next; } head=preNode; return head; } } class ListNode { int val; ListNode next; ListNode(int x) { val = x; } }
思路很常规，找到中间节点的位置，让头结点指向它就可以了，然后把头结点返回即可。
官网的方法蛮简单，蛮巧妙的，把链表用数组来存起来，然后返回指定下标的节点。
class Solution { public ListNode middleNode(ListNode head) { ListNode[] A = new ListNode[100]; int t = 0; while (head != null) { A[t++] = head; head = head.next; } return A[t / 2]; } }
此外还有快慢指针法：用两个指针 slow 与 fast 一起遍历链表。slow 一次走一步，fast 一次走两步。那么当 fast 到达链表的末尾时，slow 必然位于中间。
