Given a non-empty, singly linked list with head node head, return a middle node of linked list.

If there are two middle nodes, return the second middle node.

 

Example 1:

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.

Example 2:

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.

 

Note:

• The number of nodes in the given list will be between 1 and 100.

 

---

 

1 /** 2  * Definition for singly-linked list. 3  * struct ListNode { 4  *     int val; 5  *     ListNode *next; 6  *     ListNode(int x) : val(x), next(NULL) {} 7  * }; 8  */ 9 class Solution {10 public:11     ListNode* middleNode(ListNode* head) {12         if(head==NULL||head->next==NULL){13             return head;14         }15         16         ListNode* slow=head;17         ListNode* fast=head;18         while(fast->next&&fast->next->next){19             fast=fast->next->next;20             slow=slow->next;21         }22         23         if(fast->next==NULL){24             return slow;25         }else{26             return slow->next;27         }28     }29 };

方法二：

1 /** 2  * Definition for singly-linked list. 3  * struct ListNode { 4  *     int val; 5  *     ListNode *next; 6  *     ListNode(int x) : val(x), next(NULL) {} 7  * }; 8  */ 9 class Solution {10 public:11     ListNode* middleNode(ListNode* head) {12         ListNode* slow=head;13         ListNode* fast=head;14         while(fast&&fast->next){15             fast=fast->next->next;16             slow=slow->next;17         }18         19         return slow;20     }21 };