普通方法：
首先遍歷一遍單鏈表得到鏈表長(zhǎng)度L肖粮，再次從頭結(jié)點(diǎn)循環(huán)L/2找到結(jié)點(diǎn)。
算法復(fù)雜度（精確的復(fù)雜度）O(L+L/2) = O(3L/2)
優(yōu)化方法（快慢指針）
設(shè)置兩個(gè)指針*search 和*mid ,其中*search的移動(dòng)速度是*mid的兩倍笆包。 當(dāng)這倆都在一個(gè)循環(huán)體內(nèi)，search 指向末尾結(jié)點(diǎn)的時(shí)候，mid就正好在中間了英遭。 這也是標(biāo)尺思想
<pre>
Status GetMidNode(LinkList L, ElemType *e)
{
LinKList search ,mid;
mid = search = L
while(search->next != NULL)
{
if(search->next->next != NULL)
{
search= search->next->next; //這里移動(dòng)倆個(gè)
mid = mid->next; //這里 移動(dòng)一個(gè)
}else
{
search= search->next;
}
}
*e = mid-data;
return true;
}
</pre>
-
看我那么可愛(ài)n(≧▽≦)n
- 關(guān)注我的微薄 (梁同桌)：http://weibo.com/tongrenyinsheng
- 個(gè)人博客： www.liangtongzhuo.com
- ios 個(gè)人寫的app （同人音聲）ASMR音樂(lè)
