鏈表中環的入口結點

題目描述
給一個鏈表，若其中包含環，請找出該鏈表的環的入口結點，否則，輸出null。

分析

• 第一步：確定一個鏈表中是否有環
  我們可以用兩個指針來解決，定義兩個指針，同時從鏈表的頭結點觸發，一個指針一次走一步，另一個指針一次走兩步。如果走的塊的指針追上了走的慢的指針，那么鏈表就包含環。如果走得快的只恨走到鏈表的末尾都沒有追上走的慢的，那么鏈表就沒有環。
• 第二步：如何找到環的入口
  還是利用兩個指針來解決，先定義兩個指針p1p_1p1?和p2p_2p2?指向鏈表的頭結點，如果鏈表中的環有n個節點，那么指針p1p_1p1?現在鏈表上向前移動n步，然后兩個指針按相同速度向前移動，當第二個指針指向環的節點入口時，第一個指針已經圍繞著環走了一圈，又回到入口節點。
• 第三步：如何知道環中節點的數目
  在第一步中判斷一個鏈表里是否有環時用到一快一慢兩個指針，如果兩個指針相遇，那么有環，兩個指針相遇的節點一定在環中，那么就可以從這個節點觸發，一邊繼續向前移動一邊計數，當再次回到這個節點時就可以得到環中節點的點數。

節點類：

public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}

實現類：

public class Solution {public ListNode EntryNodeOfLoop(ListNode pHead){if(pHead == null || pHead.next == null) {return null;}ListNode meet = MeetNode(pHead);if(meet == null ) {return null;}int nodeInLoop = 1;ListNode pNode = meet, pNode2 = pHead;while(pNode.next != meet) {pNode = pNode.next;++nodeInLoop;}pNode = pHead;for (int i = 0; i < nodeInLoop; i++) {pNode = pNode.next;}while(pNode != pNode2) {pNode = pNode.next;pNode2 = pNode2.next;}return pNode;}public ListNode MeetNode(ListNode head) {if(head == null) {return null;}ListNode slow = head.next;if(slow == null) {return null;}ListNode fast = slow.next;while(fast != null && slow != null) {if(fast == slow) {return slow;}slow = slow.next;fast = fast.next;if(fast != null) {fast = fast.next;}}return null;}}