給定一個未知長度的單鏈表郊霎，快速求得其中間節(jié)點(diǎn)
示例：輸入：1->3->5->3->9
輸出：5
思路
普通解法：要找到中間結(jié)點(diǎn)，首先想到的是通過遍歷鏈表移袍，得到鏈表的長度解藻。再次遍歷鏈表，找到長度一半的位置葡盗，即為解螟左。時間復(fù)雜度為O(3/2N)
快慢指針法：定義兩個指針p1，p2，均指向頭結(jié)點(diǎn)胶背。我們讓p2的移動速度是p1的兩倍巷嚣。當(dāng)p2指向尾結(jié)點(diǎn)時，p1指向的即為中間結(jié)點(diǎn)奄妨。時間復(fù)雜度為O(1/2N)
解：(快慢指針)
class Solution {
public:
int findMidNode(ListNode *L) {
ListNode *p1=L->next; //鏈表包含頭結(jié)點(diǎn)
ListNode *p2=L->next;
while(p2->next!=NULL){
if(p2->next->next!=NULL) {
p2 = p2->next->next;
p1 = p1->next;
}
else
p2=p2->next;
}
return p1->val;
}
};
