题目描述：
- 给定一个链表，判断链表中是否有环。不使用额外空间解决
- 给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
- 求有环单链表的环长
- 求有环单链表的链表长
- 如何判断两个单链表有交？第一个交点在哪里？
image
给定一个链表，判断链表中是否有环。不使用额外空间解决
使用slow和fast两个指针遍历链表，fast的比slow快一步，当fast遍历不为null，并且fast==slow则说明单链表中存在环；
给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
image
Pos:为slow和fast第一的交点；
Join：链表开始入环的第一个结点；
x：Join到Pos的距离；
LenA： head到join的距离
R : 环的长度
第一次相遇slow走的距离：S = LenA + x；
第一次相遇fast走的距离：2S = LenA + x + nR；
由此可以得出： LenA = nR - x；
第一次碰撞点Pos到连接点Join的距离 + nR=头指针到连接点Join的距离*
因此算法为：当slow与fast第一次相遇后，将slow指向head结点，然后slow与fast以同样的速度依次遍历，再次相遇时slow指向的结点就是链表开始入环的结点
求有环单链表的环长
在环上相遇后，记录第一次相遇点为Pos，之后指针slow继续每次走1步，fast每次走2步。在下次相遇的时候fast比slow正好又多走了一圈，也就是多走的距离等于环长。
求有环单链表的链表长
Head遍历到Join的距离 + 环长 = 链表长
如何判断两个单链表有交点？第一个交点在哪里？
如果两个链表相交，那么他们最后一个结点一定相同；否则不相交； 由此可以遍历两个链表，拿到最后一个结点做对比，相同则相交，不同则不相交；
判断出两个链表相交后就是判断他们的交点了。假设第一个链表长度为len1，第二个问len2，然后找出长度较长的，让长度较长的链表指针向后移动|len1 - len2| (len1-len2的绝对值)，然后在开始遍历两个链表，判断节点是否相同即可
参考
实现代码
// 判断单链表中是否存在环
public boolean hasCycle(ListNode head) {
boolean flag = false;
ListNode fast = head;
ListNode slow = head;
while (fast !=null && fast.next !=null){
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
flag = true;
break;
}
}
return flag;
}
// 获取单链表第一次入环的结点
public ListNode getFirstNodeInCycle(ListNode head) {
if(head == null) {
return null;
} else {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if(fast == slow){
//有环，则返回环的第一个节点
slow = head;
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
}
// 求环的长度
public int cycleLength(ListNode head) {
int meet = 0;
int length = 0;
ListNode fast = head;
ListNode slow = head;
while (fast !=null && fast.next !=null){
fast = fast.next.next;
slow = slow.next;
if (fast == slow && meet==0) {
meet ++;
}
if (meet == 1){
length ++;
}
if (meet == 2){
break;
}
}
return length;
}
}
class ListNode{
int val;
ListNode next;
ListNode(int x){
val = x;
next = null;
}
}
