鏈表中環(huán)的入口結(jié)點(diǎn)

給一個(gè)鏈表，若其中包含環(huán)，請(qǐng)找出該鏈表的環(huán)的入口結(jié)點(diǎn)，否則，輸出null。

思路

兩個(gè)快慢指針從頭節(jié)點(diǎn)開(kāi)始走，

代碼

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
     public static void main(String[] args) {
       Solution s = new Solution();
       //定義一個(gè)鏈表
       ListNode p1 = new ListNode(1);
       ListNode p2 = new ListNode(2);
       ListNode p3 = new ListNode(3);
       ListNode p4 = new ListNode(4);
       ListNode p5 = new ListNode(5);
       p1.next = p2;
       p2.next = p3;
       p3.next = p4;
       p4.next = p5;
       p5.next = p3;
       s.EntryNodeOfLoop(p1);
    }

    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
       //定義兩個(gè)快慢指針
        ListNode slow = pHead;
        ListNode fast = pHead;
        if(pHead == null || pHead.next == null) return  null;
        //找出快慢指針相遇的節(jié)點(diǎn)
        do {  //這里一定要是do-while；如果是while的話slow永遠(yuǎn)等于fast
            slow = slow.next;
            fast = fast.next.next;
            if(fast == null || fast.next == null)
                return null;
        }while (slow != fast);
        //找出環(huán)入口并打印第幾個(gè)節(jié)點(diǎn)是環(huán)入口
        int count = 1;
        slow = pHead;
        while (slow != fast){ // 因?yàn)檫@里slow已經(jīng)被重新指向pHead，!=fast所以可以先判斷
            slow = slow.next;
            fast = fast.next;
            count ++;
        }
        System.out.println(count);
        //計(jì)算環(huán)的節(jié)點(diǎn)數(shù)
        int loopCount = 0;
        do {
            fast = fast.next;
            loopCount ++;
        }while(slow != fast);
        System.out.println(loopCount);
        return slow;
    }
}