链表中环的入口节点

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(slow==fast){
                slow=head;
                while(fast!=slow){
                    slow=slow.next;
                    fast=fast.next;
                }
                return slow;
                }
        }
        return null;
    }

求助：为啥对快指针的赋值需要从第二个开始？
如果我对快慢指针的赋值是：

        ListNode slow = head.; // 慢指针
        ListNode fast = head.next; // 快指针

就提示运行超时，但是如果是下面的这种就是可以的。这是为啥啊？求大佬指点一下！
下面这个代码是可以通过的

    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null) return null;
        ListNode slow = head.next; // 慢指针
        ListNode fast = head.next.next; // 快指针
        while(fast != null && fast.next != null){
            if(fast == slow) { //有环
                while(head != slow){ //从头再来
                    head = head.next;
                    slow = slow.next;
                }
                return head;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return null;
    }

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null || head.next==null) return null;
        ListNode l1=head,l2=head;
        int i=0;
        while(l2!=null && l2.next!=null){
            l1=l1.next;
            l2=l2.next.next;
            i++;
            if (l1==l2){
                l1=head;
                while(l1!=l2){
                    l1=l1.next;
                    l2=l2.next;
                }
                return l1;
            }
        }
        return null;
    }
}

public class Solution {
    public ListNode detectCycle(ListNode head) {
    	if (head == null) {
    		return null;
    	}
    	//判断是否有环
    	ListNode meetNode = meetingNode(head);
    	if (meetNode == null) {//说明无环
    		return null;
    	}
    	//计算环的大小
    	ListNode fast = meetNode;
    	ListNode slow = meetNode;
        int roll=0;
        do {
        fast = fast.next;
            roll++;
        }while (slow != fast);
        //fast先走roll-1步，然后shlow走，直到他们相遇，即为入口
        slow = head;
    	fast = head;
        while(roll>0)
        {
            roll--;
            fast=fast.next;
        }
    	while (slow != fast) {
    		slow = slow.next;
    		fast = fast.next;
    	}
    	
     	return slow;
    }
    
    //寻找相遇节点，如果无环，返回null
    public ListNode meetingNode(ListNode head) {
    	ListNode slow = head;
    	ListNode fast = head;
    	while (fast != null && fast.next != null) {
    		slow = slow.next;
    		fast = fast.next.next;
    		if (slow == fast) {
    			return slow;
    		}
    	}
    	return null;
    }
}

环儿的入口结点：从head起，第一个在环儿里的结点。

思路：爱的暴力转圈圈，时间复杂度O((n-m)*m)，n=链表长度，m=环的长度；最坏接近O(n^2)

    1）定义一对快慢指针，先让两个指针进入环中。
    若指针走的过程中转角遇到空null结点，说明没有环，return null即可。唉！没找到爱的圈圈。
    
    2）两个指针进入环中相遇后，进入下一步找环入口操作：
    从head依次往后枚举判断当前枚举的结点是否在环中，判断方法：
    让环中指针在环内转圈，若途中遇到了当前枚举的结点，说明该结点在环中。
    找到第一个这样的结点就是入口结点。

public ListNode detectCycle(ListNode head) {
        if(head!=null){
            ListNode first=head,second=head.next,start;//定义指针
            //尝试把指针拉入环中
            while(first!=second){
                if(first==null||second==null||second.next==null) return null;//没环
                first=first.next;
                second=second.next.next;
            }
            //有环
            //找环入口：从head起依次往后枚举，第一个在环里的结点就是环的入口结点
            start=second;//标记环起点
            first=head;
            while(first!=null){
                //second指针在环里转一圈，查看当前结点first是否在环里
                do{
                    if(second==first) return first;//找到的第一个就是结果
                    second=second.next;
                }while(second!=start);//转一圈退出
                first=first.next;//枚举下一个
            }
            return null;
        }
        return null;
    }

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null){
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next!=null && fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if(fast == slow){
                slow = head;
                while(slow!=fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
              break;
            }
        }
        if(fast.next == null || fast.next.next == null){ return null;}
        return slow;
    }
}

public class Solution {
    public ListNode detectCycle(ListNode head) {
        // first get the length of the circel
        // use fast and slow pointer
        //how to get the length?first meet the try again count
        if(head == null||head.next == null) return null;
        int len = 1;
        ListNode slow = head;
        ListNode fast = head.next;
        ListNode temp;
        ListNode res = head;
        while(slow!=null&&fast!=null){
            slow = slow.next;
            fast = fast.next;
            if(fast!=null){
                fast = fast.next;
            }
            if(fast == slow) break;
        }
        if(fast==null||slow==null) return null;
        temp = slow;
        while(slow.next!=temp){
            slow = slow.next;
            len++;
        }
        for(int i = 0;i<len;i++){
            res = res.next;
        }

        while(head!=res){
            head = head.next;
            res = res.next;
        }
        return res;
    }
}

//思路：和判断是否有环解法一致，将遍历后的节点指向一个新增节点，如果遍历过程中，某个节点指向了那个节点，那么这个节点就是入口节点（即交叉点）。


public static ListNode detectCycle(ListNode head) {
        ListNode target = new ListNode(-1);
        ListNode cur = head;
        while(cur != null) {
            if(cur.next == target) {
                return cur;
            }
            ListNode next = cur.next;
            cur.next = target;
            cur = next;
        }
        return null;
    }

 public ListNode detectCycle(ListNode head) {
        if (head==null) return null;
        //1.使用快慢指针方法，判定是否存在环
        //2.将两指针分别放在链表头(X)和相遇位置(Z)，并改为相同速度推进，则两指针在环开始位置相遇(Y)。
        //3.证明：首先a是起点到环的距离 b是环起点到相遇点的距离 c是相遇点到环起点的距离
        //2*(a + b) = a + b + n * (b + c)； a=(n - 1) * b + n * c = (n - 1)(b + c) +c;
        //即a = c; 下面i是慢指针 j是快指针 不涉及插入 所以不用设置哑头节点
        ListNode i = head,j = head;
        //j.next.next存在前提j.next存在 再者 要判断链表是否有尽头 仅仅看j下一步是不是空即可 i走的慢可以不管
        while (j.next!=null&&j.next.next!=null){
            //不能一上来就移动 这样i==j直接触发了 gg
            //不相等就快慢指针 分别行动直到i==j相遇再进行相应处理
            i = i.next;
            j = j.next.next;
            if (i==j) {
                ListNode temp = head;
                //i和j点相遇
                //起点位置和环位置同时每次走一步 一定会在环起点相遇 上面证明了a=c
                while (temp!=i){
                    temp = temp.next;
                    i = i.next;
                }
                //指向头节点的指针和指向相遇点的指针都相等了 说明在环起点相遇了 返回相遇节点值
                return temp;
            }
           
        }
        return null;
    }

/**
思路：
假定快慢指针，相同时间下，快指针所走路程是慢指针的两倍
当两个指针在环上相遇时，快指针比慢指针多走了n圈
减去二者在环上重叠的部分，快指针多走的距离即是直线的长度；
故此时只需要将慢指针从头走起，快指针变为慢指针继续前进，二者定会在环入口相遇
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        ListNode p1 = head;
        ListNode p2 = head;
        int step = 0;
        do {
           step++;
           p1 = p1.next;
           p2 = p2.next.next;
        } while (p1 != p2 && p2 != null && p2.next != null);
        
        if (p2 == null || p2.next == null) {
            return null;
        }
        
        p1 = head;
        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }
}

public class Solution {
    public ListNode detectCycle(ListNode head) {
      if(head==null)  return null;
      while(head.next!=null){
          if(head.next==head) return head;
          ListNode r=head.next;
          head.next=head;
          head=r;
      }
        return null;
    }
}

/**
假设X,Y,Z分别为链表起始位置，环开始位置和两指针相遇位置，则根据快指针速度为慢指针速度的两倍，可以得出：
2*(a + b) = a + b + n * (b + c)；即
a=(n - 1) * b + n * c = (n - 1)(b + c) +c;
注意到b+c恰好为环的长度，故可以推出，如将此时两指针分别放在起始位置和相遇位置，并以相同速度前进，当一个指针走完距离a时，另一个指针恰好走出 绕环n-1圈加上c的距离。
故两指针会在环开始位置相遇。
 */

public class Solution {
    public ListNode detectCycle(ListNode head) {
     if(head==null)  return null;
      ListNode slow=head;
      ListNode fast=head;
      while(fast!=null&&fast.next!=null){
          slow=slow.next;
          fast=fast.next.next;
          if(slow==fast){//相遇位置
            while(head!=slow){
                head=head.next;
                slow=slow.next;
            }
              return head;
              
          }
      }
        return null;
    }
}

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null||head.next==null) return null;
        ListNode fast = head;
        ListNode slow = head;
        //先找出相遇的位置
        while(fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            //相遇了则跳出，此时slow==fast相遇
            if(slow==fast) break;
        }
        //不相等说明无循环
        if(fast!=slow) return null;
        //慢指针重新指向首部，快指针指向相遇节点，再次循环(速度一致)
        //再次相遇时是在循环的入口节点
        slow = head;
        while(slow!=fast){
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }
}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
// 思路：先判断有没有环。在有环的情况下，再找环的入口。
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null){
            return head;
        }
        ListNode fast, slow;
        fast = slow = head;
        boolean flag = false;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                flag = true;
                break;
            }
        }
        if(flag == false){
            return null;
        }
        slow = head;
        while(slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        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;
        }
        slow = head;
        while (fast != null && slow != null) {
            if (fast == slow) {
                return fast;
            }
            fast = fast.next;
            slow = slow.next;
        }
        return null;
    }
}