# 876 - Middle of the Linked List

解法一 - Fast & Slow Pointer

這題也還滿單純的，我們可以用兩個 pointer，fast 一次走兩步，slow 一次走一步，當 fast 走到底的時候，slow 就會在中間。

不過我們還需要注意一下，linked list 長度有 even 跟 odd 兩種，以下分別解析：

• Odd:

    1->2->3->NULL

  當 slow 走到 2，fast 已經走到 3，下一次不會再進 while 迴圈，這時 return slow 就好。

• Even:

    1->2->3->4->NULL

  當 slow 走到 2，fast 走到 3，下一次因為 fast->next->next 就是 NULL 了，所以不會再進 while 迴圈，但這時要 return slow->next。

實作如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;

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

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