面試題快慢鏈表和快慢指針
更新時(shí)間：2017年06月16日 11:52:46 投稿：lqh
這篇文章主要介紹了面試題快慢鏈表和快慢指針的相關(guān)資料,需要的朋友可以參考下
騰訊的一道面試題：如何快速找到位置長(zhǎng)度單鏈表的中間節(jié)點(diǎn)？普通方法，就是先遍歷，在從頭找到2/length的中間節(jié)點(diǎn)。算法復(fù)雜度是：O(3*n/2)。而更快的方法就是利用快慢指針的原理。
快慢鏈表：利用標(biāo)尺的思想，設(shè)置兩個(gè)指針（一快一慢）*serach和*mid，剛開(kāi)始都指向單鏈表的頭結(jié)點(diǎn)。但是*search指針的移動(dòng)速度是*mid的兩倍。當(dāng)*search到尾結(jié)點(diǎn)的時(shí)候，mid剛好到了中間。算法復(fù)雜度是：O(n/2)
int GetMidNode(LinkList *L,int elem){
LinkList *search,*mid;
mid = search = L; //指向頭結(jié)點(diǎn)
while (search->next != NULL){ //當(dāng)存在下個(gè)結(jié)點(diǎn)的時(shí)候
if (search->next->next!=NULL) {//檢查下個(gè)的下個(gè)節(jié)點(diǎn)是否為空
search = search->next->next;
mid = mid->next;
}
else
search = search->next;
}
elem = mid->data;
return elem;
}
感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！
相關(guān)文章
C++實(shí)現(xiàn)線程池的簡(jiǎn)單方法示例
這篇文章主要給大家介紹了關(guān)于C++實(shí)現(xiàn)線程池的簡(jiǎn)單方法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家學(xué)習(xí)或者使用C++具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-05-05
c++項(xiàng)目中后綴名vcxproj和sln的區(qū)別及說(shuō)明
這篇文章主要介紹了c++項(xiàng)目中后綴名vcxproj和sln的區(qū)別及說(shuō)明,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-05-05
C語(yǔ)言手把手教你實(shí)現(xiàn)貪吃蛇AI（下）
這篇文章主要手把手教你實(shí)現(xiàn)C語(yǔ)言版貪吃蛇AI，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-01-01
關(guān)于Qt添加opencv和libtorch庫(kù)的問(wèn)題
這篇文章主要介紹了Qt添加opencv和libtorch庫(kù)的相關(guān)知識(shí)，兩種方法一種是通過(guò)手動(dòng)添加，一種是通過(guò)qt creator添加,需要的朋友可以參考下2022-01-01
C數(shù)據(jù)結(jié)構(gòu)循環(huán)鏈表實(shí)現(xiàn)約瑟夫環(huán)
這篇文章主要介紹了C數(shù)據(jù)結(jié)構(gòu)循環(huán)鏈表實(shí)現(xiàn)約瑟夫環(huán)的相關(guān)資料,需要的朋友可以參考下2017-05-05
C++ push方法與push_back方法常見(jiàn)方法介紹
push與push_back是STL中常見(jiàn)的方法，都是向數(shù)據(jù)結(jié)構(gòu)中添加元素，本文還將簡(jiǎn)述push對(duì)應(yīng)的stack與queue系列，常見(jiàn)方法的介紹，以及與push_back相對(duì)應(yīng)的vector系列常見(jiàn)方法介紹，感興趣的朋友跟隨小編一起看看吧2022-11-11
c++將數(shù)組名作為函數(shù)參數(shù)對(duì)數(shù)組元素進(jìn)行相應(yīng)的運(yùn)算
這篇文章主要介紹了c++將數(shù)組名作為函數(shù)參數(shù)對(duì)數(shù)組元素進(jìn)行相應(yīng)的運(yùn)算,需要的朋友可以參考下2014-05-05
今天就是圣誕節(jié)了，本文將再教大家一個(gè)圣誕項(xiàng)目——圣誕水晶球，今天這個(gè)呢代碼不多，但難度會(huì)有點(diǎn)。感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)學(xué)習(xí)2021-12-12
這篇文章主要介紹了詳解C語(yǔ)言數(shù)組越界及其避免方法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-02-02
基于Linux系統(tǒng)調(diào)用--getrlimit()與setrlimit()函數(shù)的方法
本篇文章是對(duì)在Linux系統(tǒng)中調(diào)用getrlimit()與setrlimit()函數(shù)的方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05