問題定義

兩個單向鏈表的頭指針，兩個鏈表都可能帶環(huán)
1: 判斷這兩個鏈表是否相交
2: 如果相交，給出他們相交的第一個節(jié)點。

無環(huán)情況

判斷鏈表是否相交

單鏈表相交，意味著相交結(jié)點具有相同的內(nèi)存地址，且相交結(jié)點后的所有結(jié)點是兩個鏈表共有的。
方法一：

Paste_Image.png

如果兩條單鏈表相交，則將鏈表B，連接到鏈表A后面，如圖所示（上面的鏈表是A，下面的鏈表是B），會形成環(huán)路，且鏈表B的表頭一定在環(huán)上。因此我們只需要從鏈表B開始遍歷，如果可以回到鏈表B的頭結(jié)點，則說明兩條鏈表相交。
時間復雜度：O(len(A)+len(B))
代碼如下：

// 結(jié)點
static class ListNode{
        int value;
        ListNode next;
    }

static boolean isIntersect1(ListNode h1, ListNode h2){
        boolean isinter = false;
        ListNode p1 = h1, p2 = h2;
        if(p1==null || h2==null) return false;
        // find the end node of list p1
        while(p1.next != null) p1 = p1.next;
        
        // append list p2 on the tail of p1
        p1.next = p2;
        
        // enumerate list p2 from its header
        while(p2 != null){
            if(p2 == h2) {
                isinter = true;
                break;
            }
            p2 = p2.next;
        }

        return isinter;
    }

方法二：
單鏈表相交，意味著相交結(jié)點具有相同的內(nèi)存地址，且相交結(jié)點后的所有結(jié)點是兩個鏈表共有的。因此如果兩個鏈表相交，則最后一個節(jié)點肯定是相同的，因此只需要判斷兩個鏈表的最優(yōu)一個節(jié)點是否相同。
時間復雜度： O(len(A)+len(B))

代碼如下：

static boolean isIntersect2(ListNode h1, ListNode h2){
        ListNode p1 = h1, p2 = h2;
        if(p1==null || h2==null) return false;
        ListNode last1 = p1;
        while(p1.next != null){
            last1 = p1;
            p1 = p1.next;
        }
        ListNode last2 = p2;
        while (p2.next != null){
            last1 = p2;
            p2 = p2.next;
        }
        if(last1==last2){
            return true;
        }else return false;

    }

尋找鏈表的第一個交點

先讓計算鏈表的長度，讓最長的鏈表A先走 len(A)-len(B)步，然后兩個鏈表一起走，第一個相交點，即為所求的點。

static ListNode findFisrtCrossNode(ListNode h1, ListNode h2){
        int lenA = len(h1);
        int lenB = len(h2);
        ListNode p1 = h1, p2 = h2;
        ListNode tmp = null;
        if(lenA > lenB) tmp = p1;
        else tmp = p2;
        for(int i=0; i<Math.abs(lenA-lenB); ++i){
            tmp = tmp.next;
        }
        if(lenA > lenB) p1=tmp;
        else p2 = tmp;
        
        while(p1!=null && p2!=null){
            if(p1==p2) return p1;
            p1 = p1.next;
            p2 = p2.next;
        }
        return null;
    }
static int len(ListNode h){
        int clen = 0;
        ListNode p = h;
        while (p!=null){
            p = p.next;
            ++clen;
        }
        return clen;
    }

有環(huán)情況

判斷鏈表是否有環(huán)

追逐法：
設(shè)置兩個指針 fast, slow，將其初始化為鏈表的頭結(jié)點；然后兩個節(jié)點同時向前移動，fast一次移動2步，slow一次移動一步。如果存在環(huán)，fast指針和slow指針一定相遇。

static boolean hasCycle(ListNode h){
        ListNode fast=h, slow=h;

        while(fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast==slow && slow!=null){
                return true;
            }
        }
        return false;
 }

尋找環(huán)在鏈表上的入口點

Paste_Image.png

代碼如下：

static ListNode findCycleEntry(ListNode h){
        ListNode fast=h, slow=h;
        ListNode meetNode = null;
        while(fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast==slow && slow!=null){
                meetNode = slow;
                break;
            }
        }
        ListNode p = h;
        while(p!=null && meetNode!=null){
            if(p==meetNode){
                return p;
            }
            p = p.next;
            meetNode = meetNode.next;
        }
        return null;
    }

找出帶環(huán)的兩條鏈表相交的第一個節(jié)點

分兩種情況：
1、只有一條鏈表帶環(huán)，此時兩條鏈表不可能相交；否則，由于相交結(jié)點后的所有結(jié)點由兩條鏈表共享，因此導致另一條不帶環(huán)的鏈表卻出現(xiàn)環(huán)，導出相悖的結(jié)論。
2、兩條鏈表都帶環(huán)。如果兩條鏈表相交，則他們共享同一個環(huán)！

Paste_Image.png

帶環(huán)鏈表相交，如圖所示，存在兩種情況：
1、交點在環(huán)中
2、交點不在環(huán)中

參考文獻中對該問題的解決辦法是首先找兩個鏈表的相遇點，但由于相遇點值存在于環(huán)中(利用fast,slow指針的方式得到的相遇點)，因此其方法不能解決交點不在環(huán)中的情況。

解決方法：
第一步：分別找出兩個鏈表的環(huán)入口點pos1, pos2；
第二步：如果pos1==pos2, 屬于第二種情況：交點不在環(huán)中。然后以pos1作為兩條鏈表的終點，利用求不帶環(huán)單鏈表交點的方法求出交點。
第三步：如果pos1!=pos2, 從pos1開始遍歷環(huán)中的節(jié)點，如果沒有發(fā)現(xiàn)有節(jié)點與pos2相等，則說明兩條鏈表沒有交點，否則，存在交點
第四步：分別以pos1和pos2作為終止節(jié)點，用求不帶環(huán)單鏈表交點的方法求解。其中，必然一個有解，一個無解。取有解的那一組作為我們的答案。

參考文章：

http://blog.csdn.net/linyunzju/article/details/7753548