题解 | #链表中环的入口结点#

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

    ListNode(int val) {
        this.val = val;
    }
}//节点类
*/
/*该题是很经典的题目，
主要思想是快慢指针，大致讲一下代码含义，slow和fast同时出发，slow每次走一步，fast每次走两步，
当slow和fast相遇以后，slow回到头部，此时快慢指针同时往前走，每次走一步直到相遇，那相遇的那个点就是环入口*/  数学思想：
/* 设置两个指针(fast, slow)，初始值都指向头，slow每次前进一步，fast每次前进二步，如果链表存在环，则fast必定先进入环，而slow后进入环，两个指针必定相遇。  当fast若与slow相遇时，slow肯定没有走遍历完链表，而fast已经在环内循环了n圈(1<=n)。假设slow走了s步，则fast走了2s步（fast步数还等于s 加上在环上多转的n圈），
  设环长为r，则：2s = s + nr  s=nr  设整个链表长L，入口环与相遇点距离为x，起点到环入口点的距离为a。   a + x = nr ,
  a + x = (n – 1)r +r = (n-1)r + L - a ,
  a = (n-1)r + (L – a – x)  (L – a – x)为相遇点到环入口点的距离，
  由此可知，从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点，  于是我们从链表头、与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。*/
public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode slow = pHead,fast = pHead;
                    if(pHead == null||pHead.next==null){//判断是否传入空链表
                        return null;
                    }
                    while(true){//快慢指针开始遍历链表
                        if(fast==null||fast.next==null){
                            return null;
                        }
                        slow = slow.next;//慢指针每次走一步
                        fast = fast.next.next;//快指针每次走两步
                        if(slow == fast) {//如果相遇，则退出循环
                            break;
                        }
                    }
                    slow = pHead;//慢指针回到链表头部
                    while(slow != fast){//开始循环，每次走一步，相遇的点就是环入口节点。
                        slow = slow.next;
                        fast = fast.next;
                    }
                    return slow;
    }
}