面試題快慢鏈表和快慢指針
更新時(shí)間：2017年06月16日 11:52:46 投稿：lqh
這篇文章主要介紹了面試題快慢鏈表和快慢指針的相關(guān)資料,需要的朋友可以參考下
騰訊的一道面試題：如何快速找到位置長度單鏈表的中間節(jié)點(diǎn)？普通方法，就是先遍歷，在從頭找到2/length的中間節(jié)點(diǎn)。算法復(fù)雜度是：O(3*n/2)。而更快的方法就是利用快慢指針的原理。
快慢鏈表：利用標(biāo)尺的思想，設(shè)置兩個(gè)指針（一快一慢）*serach和*mid，剛開始都指向單鏈表的頭結(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)文章
std::sort函數(shù)是C++標(biāo)準(zhǔn)庫中常用的排序函數(shù)之一,它可以對(duì)各種類型的序列進(jìn)行排序,本文就來介紹一下C++中std::sort函數(shù)介紹和使用場景,感興趣的可以了解一下2024-02-02
這篇文章主要介紹了在C語言編程中使用變量的基礎(chǔ)教程,特別需要注意C語言中的指針變量,需要的朋友可以參考下2016-02-02
C++ 是一門面向?qū)ο蟮木幊陶Z言，理解 C++，首先要理解類（Class）和對(duì)象（Object）這兩個(gè)概念。下面和小編一起來學(xué)習(xí)吧2021-09-09
C語言 動(dòng)態(tài)內(nèi)存開辟常見問題解決與分析流程
動(dòng)態(tài)內(nèi)存是相對(duì)靜態(tài)內(nèi)存而言的。所謂動(dòng)態(tài)和靜態(tài)就是指內(nèi)存的分配方式。動(dòng)態(tài)內(nèi)存是指在堆上分配的內(nèi)存，而靜態(tài)內(nèi)存是指在棧上分配的內(nèi)存2022-03-03
以下是對(duì)C++中訪問字符串的三種方法進(jìn)行了詳細(xì)的總結(jié)介紹，需要的朋友可以過來參考下，希望對(duì)大家有所幫助2013-10-10
深入解析C++的循環(huán)鏈表與雙向鏈表設(shè)計(jì)的API實(shí)現(xiàn)
這篇文章主要介紹了C++的循環(huán)鏈表與雙向鏈表設(shè)計(jì)的API實(shí)現(xiàn),文中的示例對(duì)于鏈表結(jié)點(diǎn)的操作起到了很好的說明作用,需要的朋友可以參考下2016-03-03
C++11并發(fā)編程關(guān)于原子操作atomic的代碼示例
今天小編就為大家分享一篇關(guān)于C++11并發(fā)編程關(guān)于原子操作atomic的代碼示例，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧2018-12-12
這篇文章主要為大家詳細(xì)介紹了C/C++實(shí)現(xiàn)投骰子游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-11-11
C++生成隨機(jī)數(shù)的實(shí)現(xiàn)代碼
這篇文章主要介紹了C++生成隨機(jī)數(shù)的實(shí)現(xiàn)代碼，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-04-04
這篇文章主要介紹了C語言關(guān)鍵字union的定義和使用詳解,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-02-02