LeetCode简单题分享（20）

876. 链表的中间结点

这是一个简单的链表问题，其中的核心问题就是找到中心点。

因为这个链表并不是一个双向链表，所以不能简单的考虑双指针反向遍历的想法。所以快慢指针是一个好的办法。

快慢指针的概念就是慢指针每次走一步，那么他走n次的结果就是n；

快指针每次走两步，走n次的结果就是2n。

那么当快指针走到链表末尾的 时候，也就是快指针的值为空或者快指针的下一个是空。这是慢指针指向的节点就是中心节点。

代码如下：

/**
 * 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; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        //慢指针
        ListNode slowPointer = head;
        //快指针
        ListNode fastPointer = head;
        //快指针为空或者快指针的下一个节点为空的时候跳出循环
        while(fastPointer!=null && fastPointer.next!=null){
            //慢指针走一步
            slowPointer = slowPointer.next;
            //快指针走两步
            fastPointer = fastPointer.next.next;
        }
        //返回慢指针
        return slowPointer;
    }
}