最近開始復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法，然后發(fā)現(xiàn)所有的入門書籍都是以c為基礎(chǔ)來著，?然而我被強(qiáng)制轉(zhuǎn)型成了前端工程師（誤）?那么就嘗試用js來試試吧_
注意點(diǎn)
由于使用node 如果想要運(yùn)行源代碼 請安裝node.js 或者在chrome控制臺調(diào)試吧
開始吧
先發(fā)發(fā)牢騷吧，講道理，?由于進(jìn)的是一個創(chuàng)業(yè)公司，基本屬于哪里確認(rèn)就需要填哪里的節(jié)奏，于是我就很不幸的兼職了 **前端開發(fā) ?服務(wù)器運(yùn)維 ?面試官 **這些職位，然后公司招聘對于?開發(fā)工程師的算法要求水平還是比較高的所以基本上?面試環(huán)節(jié)就以考算法為主咯 那么經(jīng)常會出一道經(jīng)典的算法和數(shù)據(jù)結(jié)構(gòu)的題目
請問單向鏈表如果在進(jìn)行修改的時候出現(xiàn)成環(huán)的情況，能不能有一個算法很快的發(fā)現(xiàn)呢？
類似上圖的結(jié)構(gòu) 出現(xiàn)了一個環(huán)，導(dǎo)致遍歷整個鏈表出現(xiàn)了不可停止的狀況也就是不符合一個算法有窮的要求了
那么考察什么呢？
- 考察單向鏈表是什么
- 考察單向鏈表遍歷的結(jié)束條件
- 考察思考算法的思維性和邏輯性
嘛，先看看有哪些回答吧
在做題過程中倒也是出現(xiàn)過很多不同的答案，比如過遍歷超過一定時間啊，或者是遍歷超過一定數(shù)量之后就算成環(huán)了，那么這樣就基本無視了鏈表這種數(shù)據(jù)結(jié)構(gòu)出現(xiàn)的意義，又比如，有些人覺得能建立一個數(shù)組存儲所有出現(xiàn)過的指針地址，然后每次訪問先進(jìn)行比較，嘛，這也是一種可行方案，但是可能就會造成大量的空間浪費(fèi)，所以還會鼓勵他想一種更好的解決方案，當(dāng)然還有比如在數(shù)據(jù)域內(nèi)添加個訪問過的記號啊，記錄總長度和鏈表長度進(jìn)行比較啊等等這種已經(jīng)完全無視鏈表結(jié)構(gòu)的答案，不過還是有些人選擇不去思考（那也就只能請你走了咯）
給個提示，賽道和跑步
當(dāng)然也不能不近人情，最好的解決方案我往往也會提示這是一種和速度有關(guān)的解決方案，不過依舊還是很難想出來來著，那么正確答案又是什么呢？
正確答案
前面提到，這是一種速度問題，可以想象，如果兩個人在操場上按照不同速度奔跑會出現(xiàn)什么情況呢？
- 直道：那么速度快的會優(yōu)先跑到終點(diǎn)（地址為null）
- 圈：那么跑的快的會繞（可能不止1圈）很多圈之后又碰到慢的那個人說，兄弟，等你好久了
答案是：建立兩個變量來記錄后繼的指針，唯一不同的是一個遍歷是依次記錄后繼指針，而第二個變量則會每次都跳過一個后繼來進(jìn)行記錄后繼指針，如果出現(xiàn)null或者兩個變量相等的情況，則結(jié)束輸出結(jié)果
后記
相比記錄所有指針的方案，最優(yōu)方案節(jié)省了大量空間，同時也節(jié)約了很多時間，當(dāng)然咯，記錄所有指針也沒有錯誤啦，只不過效率上會差很多來著
所以一個好的解決方案和數(shù)據(jù)結(jié)構(gòu)帶來的好處不止一星半點(diǎn)呢（嘛，雖然好像沒體現(xiàn)數(shù)據(jù)結(jié)構(gòu)的好處）
