找出链表中间结点的三种解法

学习的是解题的思维！

找出链表的中间结点（链接在末尾）

解题思路

数组解法
由于链表不能通过下标访问对应的结点，所以我们将所有的结点存储在数组中，这样就可以通过下标访问数组的中间元素，继而找到链表的中间结点！

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];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

复杂度分析：

• 时间复杂度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/2
        while (k < size / 2) {
            ++k;
            cur = cur.next;
        }
        return cur;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

复杂度分析：

• 时间复杂度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;//返回慢指针
    }
}
1
2
3
4
5
6
7
8
9
10
11

复杂度分析：

• 时间复杂度O(n),其中 N 是给定链表中的结点数目。
• 空间复杂度O(1),只需要常数空间存放 slow 和 fast 两个指针。

OJ链接
预告：下一篇翻转链表