题目：见leetcode876

解法

方法一：

ListNode* middleNode(ListNode* head)
{
  vector<ListNode* > A = {head};
  while(A.back()->next != NULL){
    A.push_back(A.back()->next);
  }
  return A[A.size()/2];
}

时间复杂度：n;空间复杂度：n

方法二：

ListNode* middleNode2(ListNode* head)
{
  if(head == NULL) return NULL;
  ListNode* fast = head;
  ListNode* slow = head;
  while(fast != NULL && fast->next != NULL)//①
  {
    slow = slow->next;
    fast = fast->next->next;
  }
 return slow;
}

时间复杂度：0.5n;空间复杂度：O(1)//两个指针

方法三：遍历两遍,第一遍得出链表长度,第二遍得出链表中间值

ListNode* middleNode(ListNode* head) {
        ListNode* p = head;
        int num = 1;
        while(p->next!=NULL)
        {
            p=p->next;
            num++;
        }
        p = head;
        for(int i=1;i<=num/2;i++)
        {
            p=p->next;
        }  
        return p;
    }

时间复杂度：1.5n;空间复杂度：O(1)//一个指针

拓展思考：2019/1/1

1.方法二如果要查找1/n位置的结点,如果写？
当n为2^k,则递归查找前半部分k次
当n不为2^k,待解✨