一個單鏈表，長度未知，如何快速的找出位於中間的那個元素？

01-04

設置兩個指針，p1,p2, 開始p1,p2均位於鏈接的頭部。

p1 每次步進兩步，

p2 每次步進一步

當p1到達鏈表的末尾時，p2所在的位置就是鏈表的中間元素

這個問題的題目是「一個單鏈表,長度未知,如何快速的找出位於中間的那個元素？」，但在標籤里又加上了C和C++。這就使得問題是什麼變得不是那麼清楚了，因為所謂的快速的定義在演算法中和實際計算機語言實現中是不同的。

計算機科學講究演算法，講究所謂時間複雜度和空間複雜度。在這個語境下，快速是指的是某種複雜度小，它從來不管每個指令時間長短，更不會講究計算機實際的架構與實現。

如果談論到C和C++，那麼這就是實際計算機語言實現了。在現實多數場景當中，所謂演算法對於性能的意義幾乎是微乎其微的，尤其在C/C++這種原生語言的語境下，因為原生語言的高性能放大了架構和小因素之間的作用對性能的影響。當代的計算機複雜程度已經遠遠超過單個人能夠完全精通的程度，各種體系架構的互動使得人極難通過某個簡單的原則（比如演算法時間複雜度）來得到實際的性能。

從CPU微架構的指令相關性(Instruction dependency)，亂序(Out of order execution)，寄存器重命名(Register renaming)，分支預測(Branch prediction)，到內存等級(Memory hierarchy)，緩存近鄰效應(Temporal and spatial locality of cache)，再到編譯器的優化實現與內核的參數設置。這些因素之間的相互作用使得即使是最好的程序員也經常做出看似有理但實則錯誤的對性能的判別。(Even good programmers are very good at constructing performance arguments that end up being wrong, so the best programmers prefer profilers and test cases to speculation. Martin Fowler語)

所以最好的獲得高性能的方法是採用科學方法（這裡說來，有趣的是，其實所謂計算機科學並不太科學，而更應該叫計算機數學），做測試(Profiling)得到結果，找到瓶頸，由理論知識得到假設，按假設得到新方法寫新程序，重新測試，嘗試證偽想法。而不是僅僅只是由一個看似有理的想法得到結論。

舉兩個例子：

一個是Bjarne Stroustrup的講座，舉了個例子在多數時候用std::vector，甚至在插入操作居多的情況下也不要輕易使得鏈表，結論是更多去注意數據的儲存方式而不是抽象的演算法複雜度(算是某種cache-oriented programming)，因為現代計算機十分善於處理連續存儲的數據，這個因素對性能的影響遠遠大於演算法對性能的影響。Are lists evil?

另一個是，一個簡單的Intel處理器和編譯器的互動使得一個看似非常平凡而無關的改動對性能產生明顯的影響：Replacing a 32-bit loop count variable with 64-bit introduces crazy performance deviations

類似的例子還有很多。計算機課里教的各種演算法理論使人們很容易限入理論的誤區。要想不限入這個誤區，解決的辦法是，在說到性能的時候，一定要測試，拿到性能數據，從數據中找到瓶頸再來談速度。

對於這個具體問題，如果按演算法來講，就直接通過算時間複雜度來決定，不知道長度你無法得到比O(n)更好的結果。

按實際程序來說，因素就有很多：鏈表的元素長度多少？是如何存儲的？構造和析構大概花費多少？長度的先驗分布如何？以至於計算機的一二三級緩存大小如何？這些因素不同，最佳答案也會完全不一樣。要得到較可能正確的答案我們可以用理論知識與經驗，但要真正得到準確答案則還是需要細緻的測試。

程序員看到演算法就容易High起來，但老實說外行看熱鬧，內行看門道。我一直覺得演算法這個東西用什麼精妙來形容，算得上是外行看熱鬧。

在這個問題的答案下，有兩個演算法：

分別是 @蔡嘯和 @Irons Du 提供的，很顯然前者的演算法看起來比較精妙，而後者的演算法看起來簡直就是low爆了。

但事實上，不考慮vector擴容開銷的話，這倆演算法的時間複雜度都是O(n)，前者的優勢在於其只需要倆指針空間，後者則直接把整個鏈表變成了一個vector，

也就是說後者是用空間換時間。

所以說這個看似很low的演算法也是有其意義的，因為這個很low的演算法通過指針獲取元素的次數只有n+1或n次，而前者則需要獲取n+n/2次。

當然，我們知道通過指針獲取元素的性能是極高的，而且，1.5n和n+1的時間複雜度都是O(n)。但是如果通過指針獲取元素的性能變得極差的時候（例如根本就是個遠程調用的話），那麼這種low爆的演算法就會搖身一變成為最精妙的演算法，而原來精妙的演算法又會變為最SB的做法了。

演算法沒有高下之分，場景才是最重要的。

一個程序員成熟的標誌就是從看到演算法就會high，到看到薪酬才會high，，XD，，，，

來個通俗的：

遍歷鏈表依次放入一個vector，然後訪問vector.szie()/2 的元素即可。

有尋找中間元素需求你就別用單鏈表啊親，硬要這麼搞就遍歷鏈表一次，把它轉成數組，然後愛怎麼搞怎麼搞

這道題的解法已經有不少人給出來了，這是一道LintCode原題，所以我不再啰嗦思路，直接給出程序實現的參考答案：Middle of Linked List參考答案，裡面有Java、C++、Python三種語言的實現代碼。

找中間元素是演算法與數據結構學習過程中很常見的題，看到這是題主很久以前的提問，想必題主是在學習演算法與數據結構的過程中遇到了問題求助於知乎，而不是像某些回答中說的「既然要求中間元素為什麼還要用鏈表」故意為難自己。知乎雖然是個不錯的平台，但是在學習過程中遇到問題還是儘快解決的好。像這樣在知乎上提問，如果一時沒有合適的答案，在等待的過程中就浪費了很多的時間。考慮到以上，我想在這個問題下分享兩點自己學習演算法與數據結構的經驗。

1.關於書籍

一本不錯的入門書籍可以為你搭建一個系統的理論基礎，至於具體看什麼書，還是可以根據個人的基礎的。

《演算法圖解》是唯一一本我一口氣從頭看到尾的演算法書，裡面都很多圖生動形象地描述數據結構的操作過程。這本書是很適合初學者的，而且演算法中很重要的二分、貪婪、動態規劃都有介紹的。

《數據結構與演算法分析》相對而言就詳細得多了，可以當成工具書使用，哪裡不懂看哪裡。

《演算法導論》也是很多大牛推薦的經典書籍，但是我個人認為此書難度較大，不太適合入門者。不過如果想要深入研究演算法的話，倒是可以認真去看一看。

2.動手實踐

只有在理解演算法的基礎上才能真正掌握並熟練運用演算法，那麼如何練習、檢測自己有沒有理解呢？我選擇的是在LintCode上刷題。我當時是看了一部分演算法基礎書籍，就開始刷LintCode上的簡易題。也許還有很多更好的在線測試網站，但是我覺得使用LintCode是最節約時間的，因為我遇到自己無法解決的問題時，可以直接去參考答案網站上找對應題目的答案。通過搜索引擎搜索出來的結果畢竟太雜了，針對性不好，正確率也無法立即判斷。

去年秋招求職的時候，我也經歷了很多大公司的面試，演算法與數據結構知識確實是各個公司都很關注的點，希望我的經驗也能給正在閱讀的各位提供一些幫助，幫助大家一起堅持學習下去。

因為是單鏈表，想得到中間位置的地址，唯一的方法是先得到他的前驅的地址，然後，必須先得到前驅的前驅的地址，由此，可知時間複雜度為線性。

不同步長就可以解決

問題不成立：如果單鏈表有環，何為「中間元素」？

給排名第一點贊。同時想告訴你cracking the coding interview這本書的鏈表一章還有類似題目和思路。

答不對題，摺疊也請隨意