什么是快慢指針？
快慢指針中的快慢指的是移動的步長，即每次向前移動速度的快慢。例如可以讓快指針每次沿鏈表向前移動2次，慢指針每次向前移動1次。
快慢指針的常見應用
1.判斷單鏈表是否為循環鏈表
對于初學循環鏈表者，可能開始想到的方法就是使用雙重循環。當外層循環步進一個節點時，內層循環就遍歷外層循環那節點之后的所有節點，然后比較內外循環的兩個節點。若有節點地址相等，則表明該單鏈表是有循環的，反之則不存在循環。這種方法無疑效率比較低。
而快慢指針應用于這個場景效率會明顯提高。就像生活中的一個場景：一些人繞著環形跑道跑步，有的人快點，有的人慢點，過了一段時間會發現快的人又經過慢的人身旁，這就是循環跑。那么如果是理想直線跑道的話，兩個人便不會相遇了，就沒有繞圈即循環的性質。
快慢指針的思想就是這樣。快指針每次步進多個結點（視情況而定），慢指針每次只步進一個節點。那么如果該鏈表存在循環的話，快指針一定會再次碰到慢指針，反之則不存在循環。
代碼示例：
例如長度為8，從1開始：| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 1 |
| 1 | 3 | 5 | 7 | 1 | 3 | 5 | 7 | 1 |
該方法在不借助計數器變量的情況下，實現尋找中位數的功能。原理是：快指針的移動速度若是慢指針的2倍，當快指針到達鏈表尾部時，慢指針到達中點。可以想到尾部和中點的情況和節點數的奇偶有關。例如移動次數若為x，若1+2x到達了表尾，鏈表就有奇數個節點，此時慢指針為1+x,直接返回慢指針指向的數據即可。如果快指針指向倒數第二個節點，說明鏈表節點數為偶數，這時可以根據“規則”返回上中位數（1+x內容）,下中位數（1+x+1內容）,或者上下的平均數。
代碼示例：
3.如果鏈表存在環，怎么找到環的入口點呢？
有一個單鏈表，其中可能有一個環，也就是某個節點的next指向的是鏈表中在它之前的節點，這樣在鏈表的尾部形成環。 那么問題來了，如何判斷一個鏈表是這類鏈表呢？即如果鏈表存在環，怎么找到入口點呢？ ① 如果循環方式為上圖所示，即尾部有循環，當fast（兩倍速）與slow相遇時，slow一定沒有走完鏈表。 ②如果循環入口點為頭結點，如上面表格情況，那么slow恰好遍歷一圈。 對于第一種情況（如上圖），我們從鏈表頭A點與相遇點P點分別設置一個指針，每次各走一步，兩個指針必定相遇（一定存在循環啦），且第一次相遇點就是環的入口了。 解釋：A點為出發點，fast和slow在p點相遇，所以A->B->P 步數等于P->B->P 所以A->B等于P->B 那么如果在A點和p點分別設置一個指針，每次各走一步，兩個指針就會在B點相遇，即相遇在環的入口處。 對于第二種情況，相遇點即鏈表頭，也就是環的入口了。代碼示例： 4.擴展問題 判斷兩個單鏈表是否相交，如果相交，給出相交的第一個點（兩個鏈表都不存在環）。比較好的兩個方法： ①將其中一個鏈表首尾相連，檢測另外一個鏈表是否存在環，如果存在，則兩個鏈表相交，而檢測出來的第一個入口即為相交的第一個點。 ②如果兩個鏈表相交，兩個鏈表從相交點到鏈表結束都是相同的節點，我們可以先遍歷一個鏈表嗎，直到尾部，再遍歷另外一個鏈表，如果也可以走到同樣的結尾點，則兩個鏈表相交。 這時我們記下兩個鏈表length，再遍歷一次，長鏈表節點先出發前進lengthMax-lengthMin步，之后兩個鏈表同時前進，每次一步，相遇的第一點即為兩個鏈表相交的第一個點。參考文章：http://www.cnblogs.com/hxsyl/p/4395794.html#top 百度百科 新聞熱點
疑難解答
