判断链表是否有环

题目要求

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

思路实现

我们定义两个指针吗，分别是slow,fast.slow指针每次向前移动一个节点，fast指针每次向前移动两个节点，这里我们画个图会比较好理解一些，通过列出公式我们可以得出如果从两个指针相遇的位置到链表第一次入环的位置，nam这里的距离z==x，我们就可以得出我们第一次入环的节点了，这题比较考验自己的逻辑推理能力

代码实现

全面些的代码

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        } else {
            ListNode slow = head;
            ListNode fast = head;
            ListNode first = head;
            // int count=0;
            ListNode xiangyu = new ListNode(0);
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
                // count++;
                if (slow == fast) {
                    xiangyu = slow;
                    break;
                }
            }
            if (slow != fast || (slow == fast && slow.next == null) || (slow == fast && slow.next.next == null)) {
                return null;
            }
            while (first != xiangyu) {
                first = first.next;
                xiangyu = xiangyu.next;
            }
            return first;
        }
    }
}

简化后的代码(第一次看的话可能不是很好理解)

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {// 有环
                ListNode index1 = fast;
                ListNode index2 = head;
                // 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }
}