LeetCode-876. Middle of the Linked List

      
      

       
       Input: [1,2,3,4,5]
       
       
Output: Node 3 from this list (Serialization: [3,4,5])
       
       
The returned node has value 3.  (The judge's serialization of this node is [3,4,5]).
       
       
Note that we returned a ListNode object ans, such that:
       
       
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
      
      

      
      

       
       Input: [1,2,3,4,5,6]
       
       
Output: Node 4 from this list (Serialization: [4,5,6])
       
       
Since the list has two middle nodes with values 3 and 4, we return the second one.
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
      
      

      
      

       
       class 
       
       Solution {
       
       

       
       public:
       
       
  
       
       ListNode
       
       * 
       
       middleNode(
       
       ListNode
       
       * 
       
       head) {
       
       
    
       
       ListNode 
       
       *
       
       p, 
       
       *
       
       q;
       
       
    
       
       p 
       
       = 
       
       q 
       
       = 
       
       head;
       
       
    
       
       int 
       
       n 
       
       = 
       
       0;
       
       
    
       
       while (
       
       p 
       
       != 
       
       NULL) {
       
       
      
       
       p 
       
       = 
       
       p
       
       ->
       
       next;
       
       
      
       
       n
       
       ++;
       
       
      
       
       if (
       
       n 
       
       % 
       
       2 
       
       == 
       
       0) {
       
       
        
       
       q 
       
       = 
       
       q
       
       ->
       
       next;
       
       
      }
       
       
    }
       
       
    
       
       return 
       
       q;
       
       
  }
       
       
};
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
       
       
9.
       
       
10.
       
       
11.
       
       
12.
       
       
13.
       
       
14.
       
       
15.
       
       
16.