您好,登錄后才能下訂單哦!
本篇文章為大家展示了面試題快慢鏈表和快慢指針怎樣答,內(nèi)容簡明扼要并且容易理解,絕對能使你眼前一亮,通過這篇文章的詳細介紹希望你能有所收獲。
如何快速找到位置長度單鏈表的中間節(jié)點?普通方法,就是先遍歷,在從頭找到2/length的中間節(jié)點。算法復雜度是:O(3*n/2)。而更快的方法就是利用快慢指針的原理。
快慢鏈表:利用標尺的思想,設(shè)置兩個指針(一快一慢)*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; }
上述內(nèi)容就是面試題快慢鏈表和快慢指針怎樣答,你們學到知識或技能了嗎?如果還想學到更多技能或者豐富自己的知識儲備,歡迎關(guān)注億速云行業(yè)資訊頻道。
免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。