public class ListNode {
    int val;
    ListNode next;

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


 //11.给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
    public ListNode detectCycle(ListNode head) {
        if (head == null){
            return null;
        }
        //核心：从链表头部出发, 到入口点的距离,和从快慢指针的交汇处出发, 到入口点的距离相等.
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            //快指针走两步
            fast = fast.next.next;
            //慢指针走一步
            slow = slow.next;
            if (fast == slow){
                break;
            }
        }
        if (fast == null || fast.next == null){
            //不带环
            return null;
        }
        // 循环结束之后, fast 和 slow 就已经重合了
        ListNode cur1 = head;
        ListNode cur2 = fast;
        while (cur1 != cur2){
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
 
说明：不允许修改给定的链表。
 

 解题思路：
 用数学思路，快慢指针在meetNode处是相交的结点，这时候可以计算出快慢指针之间的关系，慢指针走了L+X,快指针走了L+X+NC，2slow=fast；那么L=N*C-X，发现如果此时将meetNode和头指针重新同步遍历，最后相交结点就是环的入口结点。
 
 
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode Node;
struct ListNode *detectCycle(struct ListNode *head) {
    Node* slow = head;
    Node* fast = head;

    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;

        if(slow == fast)
        {
            Node* meet = slow;
            Node* start = head;

            while(meet != start)
            {
                meet = meet->next;
                start = start->next;
            }
            return meet;
        }
    }
    return NULL;
}

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
 
说明：不允许修改给定的链表。
 
来源：https://leetcode-cn.com/problems/linked-list-cycle-ii
 
题目分析：
 
考虑链表为空，且只有一个结点且不带环的情况
当链表是首尾连接的环
普通情况使用快慢指针找到环，再由一个新指针从头到开始向后遍历结点，直到新指针与环内指针相遇，相遇结点即为入口结点
 
过程：
 

 
 
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow=head;
        ListNode* fast=head;
        ListNode* prev=head;
        
        if(head==NULL || head->next==NULL)
        {
            return NULL;
        }
    
        while(slow!=NULL && fast!=NULL && fast->next!=NULL)
        {
            slow=slow->next;
            fast=fast->next->next;
            if(slow==fast)
            {
                break;
            }
        }
        
        if(prev==slow)
        {
            return slow;
        }
        
        while(prev !=NULL && slow != NULL)
        {
            prev=prev->next;
            slow=slow->next;
            if(prev==slow)
            {
                return prev;
            }
        }
        
        return NULL;
        
        
    }
};

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 
package Test;

public class D2 {
    private ListNode getIntersect(ListNode head){
    ListNode tortoise = head;
    ListNode hare = head;
        while (hare != null && hare.next != null) {
        tortoise = tortoise.next;
        hare = hare.next.next;
        if (tortoise == hare) {
            return tortoise;
        }
    }
        return null;
}
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode intersect = getIntersect(head);
        if (intersect == null) {
            return null;
        }
        ListNode ptr1 = head;
        ListNode ptr2 = intersect;
        while (ptr1 != ptr2) {
            ptr1 = ptr1.next;
            ptr2 = ptr2.next;
        }
        return ptr1;
    }
}