找出链表中间结点的三种解法
初阶链表刷题
注意！！！
学习的是解题的思维！
找出链表的中间结点（链接在末尾）
解题思路
数组解法
由于链表不能通过下标访问对应的结点，所以我们将所有的结点存储在数组中，这样就可以通过下标访问数组的中间元素，继而找到链表的中间结点！
1.开辟一个数组用来存放结点
2.遍历链表，将链表中的元素逐个放入数组中
3.当链表为null时退出循环
4.返回数组的中间元素
因为数组长度是从0开始的，所以当我的链表为null时我的数组长度是
size=5，5/2=2，如果链表长度是偶数，是4的话，4/2=2，找到的结点依旧是第三个结点.
代码如下
class Solution {public ListNode middleNode(ListNode head) {//创建一个数组，类型是ListNode类，数组大小为100，ListNode[] A = new ListNode[100];int size = 0;while (head != null) {A[sisze++] = head;head = head.next;}return A[size / 2];}
}
复杂度分析：
- 时间复杂度O(n),其中
N是给定链表中的结点数目。 - 空间复杂度O(n),即数组
A用去的空间
单指针解法
我们可以对方法一进行空间优化，省去数组 A。
我们可以对链表进行两次遍历。第一次遍历时，我们统计链表中的元素个数 N；第二次遍历时，我们遍历到第 N/2 个元素（链表的首节点为第 0 个元素）时，将该元素返回即可。
1.遍历整个链表，记录链表的长度
2.将链表按照总长度的一半再走一遍，直到循环结束
第一遍
遍历单链表记录单链表长度
第二遍
找到中间结点
因为链表长度是从0开始的，所以当我的链表为null时我的
size长度是size=5，5/2=2，如果链表长度是偶数，是4的话，4/2=2，找到的结点依旧是第三个结点.
代码如下
class Solution {public ListNode middleNode(ListNode head) {int size = 0; //用于记录链表长度ListNode cur = head;////遍历链表求出链表的长度while (cur != null) {++size;cur = cur.next;}int k = 0;//重新从头开始向后遍历cur = head;//因为k是从0开始的，所以只需要小于size/2就行//如果k是1开始，那么就是k<=size/2while (k < size / 2) {++k;cur = cur.next;}return cur;}
}
复杂度分析：
- 时间复杂度O(n),其中
N是给定链表中的结点数目。 - 空间复杂度O(1),只需要常数空间存放变量和指针
双指针进阶解法
1.定义两个指针，一个快指针，一个慢指针。
2.快指着一次走两步，慢指针一次走一步
3.考虑快指针指向哪里时，我们的慢指针刚好走到中间结点
问：那我们可不可以再去优化一下这个解法，让他只遍历一遍就找到该链表的中间结点？
我们可以继续优化方法二，用两个指针 slow 与 fast 一起遍历链表。slow 一次走一步，fast 一次走两步。那么当 fast 到达链表的末尾时，slow 必然位于中间。
1.定义快慢指针
2.快指针一次走一步，慢指针一次走两步
3.当快指针为null或快指针的next为null时退出循环
前提讲到了，如果有两个中间结点，则返回第二个中间结点，所以我们再看一下这个解法对于结点个数为偶数个的还是否合适
看图可以知道，无论该链表是奇数个还是偶数个，都不会影响最终的结果。
判断条件：
当fast==null时，或者fast.next==null时，退出循环。
注意：由于逻辑运算符&&是先判断左侧，左侧为真再去判断右侧，如果我的fast已经是null，那么如果我将fast.next写在左侧就会产生空指针异常，所以我们需要先判断fast是否为null，也就是将fast!=null写在左侧
代码如下
class Solution {public ListNode middleNode(ListNode head) {//定义两个指针，一个快指针，一个慢指针ListNode slow = head, fast = head;while (fast != null && fast.next != null) {slow = slow.next;//慢指针一次走一步fast = fast.next.next;//快指针一次走两步}return slow;//返回慢指针}
}
复杂度分析：
- 时间复杂度O(n),其中
N是给定链表中的结点数目。 - 空间复杂度O(1),只需要常数空间存放 slow 和 fast 两个指针。
OJ链接
预告：下一篇翻转链表