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

    }

```