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