（链表）07-链表中环的入口结点

 1 /*
 2  public class ListNode {
 3     int val;
 4     ListNode next = null;
 5 
 6     ListNode(int val) {
 7         this.val = val;
 8     }
 9 }
10 */
11 public class Solution {
12 
13     public ListNode EntryNodeOfLoop(ListNode pHead) {
14         // 快指针从头节点开始遍历
15         ListNode fast = pHead;
16         // 慢指针从相遇位置开始遍历
17         ListNode slow = hasCycle(pHead);
18         // 没有环
19         if (slow == null) {
20             return null;
21         }
22         // 有环则相遇位置就是环的入口
23         while(fast != slow) {
24             fast = fast.next;
25             slow = slow.next;
26         }
27         return fast;
28     }
29 
30     public ListNode hasCycle(ListNode head) {
31         // 定义临时变量-快慢两个指针
32         ListNode fast = head;
33         ListNode slow = head;
34         // 循环链表
35         while (fast != null && fast.next != null) {
36             // 快指针走两步
37             fast = fast.next.next;
38             // 慢指针走一步
39             slow = slow.next;
40             // 快慢指针相遇则说明有环-返回相遇位置的节点
41             if (fast == slow) {
42                 return fast;
43             }
44         }
45         // 链表遍历到尾节点说明没有环
46         return null;
47     }
48 }