LintCode 带环链表

给定一个链表，判断它是否有环。

参考了网上一些资料，算是一个总结。
感谢sunflower_Yolanda的文章。

由这个问题可以引申出来几个问题，先解决本身。
1.判断是否有环。
利用两个指针slow、fast。初始时，两个指针都在表头。slow每次走一步，fast每次走两步。如果不存在环，那么fast一定先到达链表末尾。如果存在环，那么fast和slow一定会在环上的某个位置相遇。
代码：

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */


public class Solution {
    /*
     * @param head: The first node of linked list.
     * @return: True if it has a cycle, or false
     */
    public boolean hasCycle(ListNode head) {
        // write your code here
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null &&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                return true;
            }
        }
        return false;

    }
}

2.求环的长度。
第一种解法：slow与fast第一次相遇之后，继续运动，那么再一次相遇时，slow走过的长度就是环的长度。
可以这么理解：在操场绕圈跑步，fast的人是slow的人的速度的2倍，那么同时同一地点开始跑，下一次相遇一定是回到了起点，slow的人跑了1圈。

第二种解法：来自sunflower_Yolanda的文章，根据他的图很容易理解。

这里有一个问题，就是在第一次相遇时，slow一定是没走完整个环。
假设slow刚进入环，此时fast在环中比slow远的距离是x，设环长L。那么到第一次相遇，就是说 fast需要追上L-x这么长，那么每次追1步，需要L-x步。也就是slow从进入环到第一次相遇走了L-x步，环长L，自然没有走完整个环。

3.求第一个环上的点。
来自sunflower_Yolanda的文章，根据他的图很容易理解。
代码：

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */


public class Solution {
    /*
     * @param head: The first node of linked list.
     * @return: The node where the cycle begins. if there is no cycle, return null
     */
    public ListNode detectCycle(ListNode head) {
        // write your code here
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null &&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){//第一次相遇时
                ListNode t=head;
                while(t!=slow){//相遇之后，slow继续走，t从head出发，知道二者相遇，那个点就是环上第一个点。
                    t=t.next;
                    slow=slow.next;
                }
                return t;
            }
        }
        return null;
    }   
}

4.判断两个链表是否有交叉。这也是LintCode上的一道题。
将其中一个链表的尾部指向头部。然后判断另一个链表是否存在环即可。若存在，那么有交叉，否则无交叉。