LeetCode刷题--环形链表（二）

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

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

/**
 * 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;
      }
      //定义一个快指针，慢指针，判断有无环
      //快指针每次走两步，慢指针每次走一步
      //设在环状列表入口前有a个节点，环形里面有b个节点，链表总共有a+b个节点
      //那么在相遇时，fast指针走了s+nb步
      //fast是slow的步数两倍，所以f = s+nb = 2s
      //f = 2nb, s= nb，这是第一次相遇时两个指针走的步数
      //此时我们想知道环形的入口，s已经走了nb步，我们只要再让s走a步数停下来，
      //把这个链表的环状走完，他（s)就从链表口，也就是环形入口那里出来了
      //就可以知道链表环状入口在哪里了
      //依旧使用双指针的方法，我们定义一个指针，从头开始走，陪着s走a步，在环状入口他们就会第二次相遇
      //因为他们一起把链表走完了
      ListNode fast = head;
      ListNode slow =head;
      while(true){
          if(fast.next == null || fast.next.next == null){
           return null;
          }
          fast = fast.next.next;
          slow = slow.next;
          if(fast == slow){break;}
      }
      fast = head;
       while(fast != slow){
           fast = fast.next;
           slow = slow.next;
       }
       return fast;
}
}

我的理解就是：第一次相遇只是为了让slow指针放在nb步数的位置上，第二次相遇的fast指针，为了助于理解，可以用其他的变量名称来代替，它是陪着slow走了a步，构造第二次相遇。
为了更好说明，下面附上几张比较重要的图，