題目描述：

• 給定一個(gè)鏈表，判斷鏈表中是否有環(huán)。不使用額外空間解決
• 給定一個(gè)鏈表沃疮，返回鏈表開始入環(huán)的第一個(gè)節(jié)點(diǎn)。如果鏈表無(wú)環(huán)梅肤，則返回 null司蔬。
• 求有環(huán)單鏈表的環(huán)長(zhǎng)
• 求有環(huán)單鏈表的鏈表長(zhǎng)
• 如何判斷兩個(gè)單鏈表有交？第一個(gè)交點(diǎn)在哪里姨蝴？

image

給定一個(gè)鏈表俊啼，判斷鏈表中是否有環(huán)。不使用額外空間解決

使用slow和fast兩個(gè)指針遍歷鏈表似扔，fast的比slow快一步吨些，當(dāng)fast遍歷不為null搓谆，并且fast==slow則說明單鏈表中存在環(huán)；

給定一個(gè)鏈表豪墅，返回鏈表開始入環(huán)的第一個(gè)節(jié)點(diǎn)泉手。如果鏈表無(wú)環(huán)，則返回 null偶器。

image

Pos:為slow和fast第一的交點(diǎn)斩萌；
Join：鏈表開始入環(huán)的第一個(gè)結(jié)點(diǎn)；
x：Join到Pos的距離屏轰；
LenA： head到j(luò)oin的距離
R : 環(huán)的長(zhǎng)度
第一次相遇slow走的距離：S = LenA + x颊郎；
第一次相遇fast走的距離：2S = LenA + x + nR；
由此可以得出： LenA = nR - x霎苗；
第一次碰撞點(diǎn)Pos到連接點(diǎn)Join的距離 + nR=頭指針到連接點(diǎn)Join的距離*
因此算法為：當(dāng)slow與fast第一次相遇后姆吭，將slow指向head結(jié)點(diǎn)，然后slow與fast以同樣的速度依次遍歷唁盏，再次相遇時(shí)slow指向的結(jié)點(diǎn)就是鏈表開始入環(huán)的結(jié)點(diǎn)

求有環(huán)單鏈表的環(huán)長(zhǎng)

在環(huán)上相遇后内狸，記錄第一次相遇點(diǎn)為Pos，之后指針slow繼續(xù)每次走1步厘擂，fast每次走2步昆淡。在下次相遇的時(shí)候fast比slow正好又多走了一圈，也就是多走的距離等于環(huán)長(zhǎng)刽严。

求有環(huán)單鏈表的鏈表長(zhǎng)

Head遍歷到Join的距離 + 環(huán)長(zhǎng) = 鏈表長(zhǎng)

如何判斷兩個(gè)單鏈表有交點(diǎn)昂灵？第一個(gè)交點(diǎn)在哪里？

如果兩個(gè)鏈表相交舞萄，那么他們最后一個(gè)結(jié)點(diǎn)一定相同眨补；否則不相交； 由此可以遍歷兩個(gè)鏈表鹏氧，拿到最后一個(gè)結(jié)點(diǎn)做對(duì)比渤涌，相同則相交佩谣，不同則不相交把还；

判斷出兩個(gè)鏈表相交后就是判斷他們的交點(diǎn)了。假設(shè)第一個(gè)鏈表長(zhǎng)度為len1茸俭，第二個(gè)問len2吊履，然后找出長(zhǎng)度較長(zhǎng)的，讓長(zhǎng)度較長(zhǎng)的鏈表指針向后移動(dòng)|len1 - len2| (len1-len2的絕對(duì)值)调鬓，然后在開始遍歷兩個(gè)鏈表艇炎，判斷節(jié)點(diǎn)是否相同即可

參考

判斷兩個(gè)鏈表是否相交并找出交點(diǎn)

求有環(huán)單鏈表中的環(huán)長(zhǎng)、環(huán)起點(diǎn)腾窝、鏈表長(zhǎng)

實(shí)現(xiàn)代碼

     // 判斷單鏈表中是否存在環(huán)
    public boolean hasCycle(ListNode head) {
        boolean flag = false;
        ListNode fast = head;
        ListNode slow = head;
        while (fast !=null && fast.next !=null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                flag = true;
                break;
            }
        }
        return flag;
    }

     // 獲取單鏈表第一次入環(huán)的結(jié)點(diǎn)
    public ListNode getFirstNodeInCycle(ListNode head) {
        if(head == null) {
            return null;
        } else {
            ListNode fast = head;
            ListNode slow = head;
            while(fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
                if(fast == slow){
                    //有環(huán)缀踪，則返回環(huán)的第一個(gè)節(jié)點(diǎn)
                    slow = head;
                    while(slow != fast){
                        slow = slow.next;
                        fast = fast.next;
                    }
                    return slow;
                }
            }
            return null;
        }
    }

    // 求環(huán)的長(zhǎng)度
    public int cycleLength(ListNode head) {
        int meet = 0;
        int length = 0;
        ListNode fast = head;
        ListNode slow = head;
        while (fast !=null && fast.next !=null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow && meet==0) {
                meet ++;
            }
            if (meet == 1){
                length ++;
            }
            if (meet  == 2){
                break;
            }
        }
        return length;
    }
}
class ListNode{
    int val;
    ListNode next;
    ListNode(int x){
        val = x;
        next = null;
    }
}