<code>給定一個帶有頭結點 head 的非空單鏈表，返回鏈表的中間結點。
如果有兩個中間結點，則返回第二個中間結點。
示例 1：
輸入：[1,2,3,4,5]
輸出：此列表中的結點 3 (序列化形式：[3,4,5])
返回的結點值為 3 。 (測評系統對該結點序列化表述是 [3,4,5])。
注意，我們返回了一個 ListNode 類型的對象 ans，這樣：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：
輸入：[1,2,3,4,5,6]
輸出：此列表中的結點 4 (序列化形式：[4,5,6])
由於該列表有兩個中間結點，值分別為 3 和 4，我們返回第二個結點。
提示：
給定鏈表的結點數介於 1 和 100 之間。
/<code>
今天的題目只是個Easy的難度，的確也比較Easy。其實我一直在想，這個題的難度在哪裡。我覺得，如果給你一個數組，找到中位數輸出，應該每個人都會吧。為什麼鏈表就不會呢？在於很多人對鏈表的理解不夠透徹。這裡我們複習下鏈表跟數組的一些差別。數組一般都是固定長度的，每個位置都可以直接O(1)複雜度訪問，但是數組一個問題在於，插入的時候，要把後面的數據往後挪一個坑。而鏈表並沒有下標，只有一個指向下一個元素的指針。所以想要訪問第n個，只能夠不停往後遍歷。而鏈表插入的時候，就不像數組那麼麻煩了，只要修改當前結點指向新結點，新結點指向原來的下一個結點即可。
讓我們來找一個鏈表的中位數，最簡單的方法。當然可以遍歷鏈表的長度，然後再找到中位數，然後再從頭開始，遍歷中位數個，最後返回結果即可。當然這種寫法太Low了。這種鏈表的題目，我們有個高大上的寫法，就是使用兩個指針，一個每次走兩步，一個每次走一步，當走得快的走到頭了，走得慢的不就剛好走到中位數了麼？同樣的道理，如果我們要求1/4，4/5，都可以使用類似的方法。下面是一個簡單的代碼展示。
快慢指針，在我們的面試中非常地常見。據另外一個例子，如果在一個鏈表中探測有沒有存在環？在一個無環的鏈表中，快指針走到底了，慢指針還在路上。所以，如果存在環，那可定是快指針走不到底了，他還會在路上重新遇到慢指針。所以我們只要判斷快指針能否跟慢指針相遇即可。
分享到:
閱讀更多 沙茶敏碎碎念 的文章
