問題定義

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

無環(huán)情況

判斷鏈表是否相交

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

Paste_Image.png

如果兩條單鏈表相交核芽，則將鏈表B，連接到鏈表A后面酵熙，如圖所示（上面的鏈表是A轧简，下面的鏈表是B），會(huì)形成環(huán)路匾二，且鏈表B的表頭一定在環(huán)上哮独。因此我們只需要從鏈表B開始遍歷拳芙，如果可以回到鏈表B的頭結(jié)點(diǎn)，則說明兩條鏈表相交皮璧。
時(shí)間復(fù)雜度：O(len(A)+len(B))
代碼如下：

// 結(jié)點(diǎn)
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é)點(diǎn)具有相同的內(nèi)存地址，且相交結(jié)點(diǎn)后的所有結(jié)點(diǎn)是兩個(gè)鏈表共有的悴务。因此如果兩個(gè)鏈表相交睹限，則最后一個(gè)節(jié)點(diǎn)肯定是相同的，因此只需要判斷兩個(gè)鏈表的最優(yōu)一個(gè)節(jié)點(diǎn)是否相同讯檐。
時(shí)間復(fù)雜度： 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;

    }

尋找鏈表的第一個(gè)交點(diǎn)

先讓計(jì)算鏈表的長度羡疗，讓最長的鏈表A先走 len(A)-len(B)步，然后兩個(gè)鏈表一起走别洪，第一個(gè)相交點(diǎn)叨恨，即為所求的點(diǎn)。

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è)置兩個(gè)指針 fast, slow蕉拢，將其初始化為鏈表的頭結(jié)點(diǎn)特碳；然后兩個(gè)節(jié)點(diǎn)同時(shí)向前移動(dòng)诚亚，fast一次移動(dòng)2步晕换，slow一次移動(dòng)一步。如果存在環(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)在鏈表上的入口點(diǎ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)的兩條鏈表相交的第一個(gè)節(jié)點(diǎn)

分兩種情況：
1、只有一條鏈表帶環(huán)凭豪，此時(shí)兩條鏈表不可能相交焙蹭；否則，由于相交結(jié)點(diǎn)后的所有結(jié)點(diǎn)由兩條鏈表共享嫂伞，因此導(dǎo)致另一條不帶環(huán)的鏈表卻出現(xiàn)環(huán)孔厉，導(dǎo)出相悖的結(jié)論。
2末早、兩條鏈表都帶環(huán)烟馅。如果兩條鏈表相交，則他們共享同一個(gè)環(huán)然磷！

Paste_Image.png

帶環(huán)鏈表相交郑趁，如圖所示，存在兩種情況：
1姿搜、交點(diǎn)在環(huán)中
2寡润、交點(diǎn)不在環(huán)中

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

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

參考文章：

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