1.給定兩個鏈表，判斷是否有相交。
思路：首先明確一點，如果兩個鏈表相交，那麼從第一個交點開始到尾結點結束，所有的結點都是公共結點。
這也就是說，如果兩個鏈表相交，那麼這兩個鏈表的尾結點肯定是公共結點，如果尾結點不是公共結點，那麼這兩個鏈表肯定不相交。
所以我們可以如下操作：依次遍歷兩個鏈表，最後判斷尾結點是否相同，如果相同，則相交，如果不相同，則不相交。
復雜度：時間：O(m+n),m,n分別為兩個鏈表的長度；空間：O(1)
2.給定兩個鏈表，找到第一個公共結點。
思路：我們最容易想到的是從尾結點開始挨個向前比較，最後一個相同的就是第一個公共結點。
但是單鏈表只能從前往後進行遍歷，如果想要從後往前的話則需要先從前向後遍歷一次，同時用棧來記錄每一個結點，最後出棧，然後挨個對比，這樣的確可行，但是卻要額外付出O(m+n)的空間。
仔細想想，我們可以先分別遍歷兩個單鏈表，記錄長度m和n（無妨假設m>n），然後先讓長度為m的鏈表向後走(m-n)步，接著兩個鏈表同時向後遍歷，第一個相同的結點就是要求的第一個公共結點。
復雜度：O(m+n),m,n分別為兩個鏈表的長度；空間：O(1)
擴展：有的面試官為了考察學生的思維能力，會在上面基礎上，要求每個鏈表只能遍歷一次，可以對鏈表做任何修改。
這個也很簡單，解法見：http://blog.csdn.net/alexander_xfl/article/details/12560249
3.給定一個鏈表，判斷是否有環。
思路：這個是一個經典的問題了，思路也很簡單，我們首先設置兩個指針p1，p2同時指向鏈表的頭部，然後p1每次向後走1步，p2每次向後走2步。
如果有環，那麼有一步會出現p1=p2，如果p2已經到達了尾結點，則無環。
復雜度：時間：O(n),n是鏈表的長度；空間：O(1)
4.給定一個鏈表，找出環的入口位置。
思路：這個和3問題的基本思路一樣，只是需要多做一步，那就是當p1=p2的時候，將p1重新指向鏈表的頭結點，然後p1和p2都每次向後走一步，下一次p1=p2的結點就是環的入口。
復雜度：時間：O(n),n是鏈表的長度；空間：O(1)
這是在筆試面試中遇到的關於環的一些問題，今天總結了一下，供大家參考，算是了卻了一樁心事。
