推薦大家看下《編程之美》辜羊、《程序員面試金典》
還有編程相關網站：leetcode
老師講的很多題其實就是這些書和網站的題
單鏈表是否存在環(huán)米辐？環(huán)的入口是什么？
是否存在環(huán)
判斷是否存在環(huán)：設置快慢指針fast和slow淮逊，fast步速為2咒循，slow為1，若最終fast==slow干发，那么就證明單鏈表中一定有環(huán)朱巨。如果沒有環(huán)的話，fast一定先到達尾節(jié)點
簡單證明：利用相對運動的概念枉长，以slow為參考點（靜止不動）冀续，那么fast的步速實際為1琼讽，當fast超過slow之后，fast以每步一個節(jié)點的速度追趕slow洪唐，如果鏈表有環(huán)的話钻蹬，fast一定會追趕到slow，即fast==slow凭需。
如何找到環(huán)的入口
字母代表的量：
- a：鏈表頭結點到環(huán)入口的距離
- r：環(huán)長
- 藍色線：fast指針所走的距離2s
- 黑色線：slow指針所走的距離s
假設鏈表總長度為L问欠，且fast與slow相遇時fast已經繞環(huán)走了n圈，則有如下關系：
2s = s + nr
將s移到左邊得：
s = nr
轉換：
s = (n-1)r + r = (n-1)r + L-a
a+x = (n-1)r + L-a
得：
a = (n-1)r + L-a-x
由圖可知功炮，（L-a-x）為相遇點到環(huán)入口點的距離溅潜。由上式可知：
從鏈表頭到環(huán)入口的距離 = （n-1）圈內環(huán)循環(huán) + 相遇點到環(huán)入口點的距離
將r視為周期的話，a與L-a-x在某種意義上是相等的（實際并不一定相等）薪伏。
那么由此我們便找到了突破點滚澜，為了找到環(huán)的入口點，在fast與slow相遇時嫁怀，將slow指針重新指向單鏈表的頭節(jié)點设捐，fast仍然留在相遇點，只不過步速降為與slow相同的1塘淑，每次循環(huán)只經過一個節(jié)點萝招，如此，當fast與slow再次相遇時存捺，那個新的相遇點便是我們苦苦尋找的入口點了槐沼。
如何知道環(huán)的長度
紀錄下相遇點，讓slow與fast從該點開始捌治，再次碰撞所走過的操作數就是環(huán)的長度r岗钩。
帶環(huán)的鏈表的長度是多少？
通過以上分析我們已經知道了如何求環(huán)入口肖油，環(huán)長兼吓，那么鏈表長度顯然就是兩者之和，即：
L = a + r
判斷兩個鏈表是否相交
分析問題之前我們要搞清楚鏈表相交的一些基本概念
- 明確概念：兩個單向鏈表相交森枪，只能是y型相交视搏，不可能是x型相交。
- 分析：有兩個鏈表县袱，La,Lb,設他們的交點設為p浑娜，假設在La中，p的前驅為pre_a式散，后繼為next_a,在Lb中棚愤，前驅為pre_b,后繼為next_b，則
pre_a->next=p,pre_b->next=p,接下來看后繼,p->next=next_a,p->next=next_b；那么問題就出來了宛畦，一個單鏈表的next指針只有一個瘸洛，
怎么跑出兩個來呢，所以必有next_a==next_b次和，于是我們得出兩個鏈表相交只能是Y型相交反肋。明確了這個概念，我們再來堆相交問題進行分析踏施。
情況一：兩個鏈表都無環(huán)
- 問題簡化石蔗。將鏈表B接到鏈表A的后面，如果A畅形、B有交點养距，則構成一個有環(huán)的單鏈表，而我們剛剛在上面已經討論了如何判斷一個
單鏈表是否有環(huán)日熬。 - 若兩個鏈表相交則必為Y型棍厌，由此可知兩個鏈表從相交點到尾節(jié)點是相同的，我們并不知道他們的相交點位置竖席，但是我們可以遍歷得出A耘纱、B鏈表的
尾節(jié)點，如此毕荐，比較他們的尾節(jié)點是否相等便可以求證A束析、B是否相交了。
情況二：鏈表有環(huán)
其中一個鏈表有環(huán)憎亚，另外一個鏈表無環(huán)员寇。則兩個鏈表不可能相交。（啥第美？你不知道為啥蝶锋？自己看看前面的“明確概念”反省吧）
那么有環(huán)相交的情況只有當兩個鏈表都有環(huán)時才會出現，如果兩個有環(huán)鏈表相交斋日，則他們擁有共通的環(huán)牲览，即環(huán)上任意一個節(jié)點都存在于
兩個鏈表上墓陈。因此恶守，通過判斷A鏈表上的快慢指針相遇點是否也在B鏈表上便可以得出兩個鏈表是否相交了。
求相交鏈表的相交點
題目描述：如果兩個無環(huán)單向鏈表相交贡必，怎么求出他們相交的第一個節(jié)點呢兔港？
分析：采用對齊的思想。計算兩個鏈表的長度 L1 , L2仔拟，分別用兩個指針 p1 , p2 指向兩個鏈表的頭衫樊，然后將較長鏈表的 p1（假設為 p1）向后移動L2 - L1個節(jié)點，然后再同時向后移動p1 , p2，直到 p1 = p2科侈。相遇的點就是相交的第一個節(jié)點载佳。
