题目

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。

思路

使用快慢指针法，初始时快慢指针都指向头结点，然后快指针走两步，慢指针走一步，当快指针无法在走时，分为两种情况：

1. 快指针指向最后一个结点，链表为奇数长度，此时慢指针指向中间结点。
2. 快指针指向倒数第二个结点，链表为偶数长度，慢指针指向中间左边的结点。

时间复杂度O(n)
空间复杂度O(1)

c++代码

 ListNode* middleNode(ListNode* head) {
        ListNode *fast=head, *slow = head;

        while(fast->next != NULL && fast->next->next != NULL)
        {
            fast = fast->next->next;
            slow = slow->next;
        }

        if(fast->next == NULL)     return slow;
        else          return slow->next;

    }

下面的代码和上面的代码思路是一样的，但是循环判断条件不同，但是运行结果相差很大，下面的代码时间和内存消耗都比上面的少。。

 ListNode* middleNode(ListNode* head) {
        ListNode *fast=head, *slow = head;

          while(fast != NULL && fast->next != NULL)
        {
            fast = fast->next->next;
            slow = slow->next;
        }

        return slow;
    }