https://leetcode.com/problems/middle-of-the-linked-list/description/
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.
中文翻譯:
給你一個link-list, 回傳位於中間位置的那個node
[Solution]
Using 2 pointers strategy to increase performance.
We use 2 pointers to traverse this link list simultaneously.
Pointer1: 1 step forward at a time.
Pointer2: 2 steps forward at a time.
Pointer2's speed is 2 times faster than pointer1.
After k times, p2 will move 2k steps, and p1 will move k steps.
When p2 reach the end point of the list, p1 will reach the middle point (of the list).
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode *p1=head,*p2=head;
while(p2 && p2->next){
p2=p2->next->next;
p1=p1->next;
}
return p1;
}
};
