判断链表环相关的面试题

题目1：判断链表是否有环

       首先应判断两个单链表是否含有环，判断是否有环的方法很多，目前最好的方法是：一开始设置两个指针都指向表头，其中一个每次（一步）前进一个节点的叫p1，另外那个每次（一步）前进两个节点的叫p2 。p1和p2同时走，当其中有一个遇到null，就证明链表没有环。如何某个时刻（假设走了n步之后），p1和p2指向的地址相同，那么链表就是有环的。

//判断链表是否有环
public boolean hasLoop(Node head) {
    Node first = head;
    Node second = head;
    //判断条件second在前，second.next在后，否则可能会报空指针异常
    while(second != null && second.next != null  ) {
        first = first.next;
        second = second.next.next;
        if(first == second)
            return true;
    }
    return false;
}

题目2：如果链表有环，求环的长度：

       若链表无环，则其长度为0；若链表有环，则second和first指针相遇时，相遇点一定在环中。记录下相遇点，first再次走到该点时走到长度即为所求。

//首先得到相遇点
private Node getMeetNode(Node head) {
    Node first = head;
    Node second = head;
    //判断条件second在前，second.next在后，否则可能会报空指针异常
    while(second != null && second.next != null  ) {
        first = first.next;
        second = second.next.next;
        if(first == second)
            return first;
    }
    return null;
}

public int getLoopLength(Node head) {

    Node meetNode = getMeetNode(head);//获取相遇点的指针
    if(meetNode == null) //无环
        return 0;
    Node first = meetNode.next;
    int result = 1;
    while(first != meetNode) {
        result++;
        first = first.next;
    }
    return result;
}

题目3：链表环的入口点：

       根据结论：从两个指针相遇点 和 两个指针头结点 这两个位置出发，走相同的步长，他们的相遇点就是环的入口点。具体推导过程见这里点击打开链接。

       定义两个指针first、second，让first先走 len 步，然后first和second一起向前走，两者必然会相遇，相遇点即为环的入口结点。

public Node entryNodeOfLoop(Node head){

    Node first = head;
    Node second = head;
    int len = getLoopLength(head);
    if(len == 0)
        return null;
    for(int i=0; i=0?getNode(h1,h2,len1,len2):getNode(h2, h1, len2, len1);  
}  
  
private Node getNode(Node h1, Node h2, int len1, int len2) {  
    int i = 0;  
    while (i < len1 - len2) {  
        h1 = h1.next;  
    }  
    while (true) {  
        h1 = h1.next;  
        h2 = h2.next;  
        if (h1 == h2)  
        return h1;  
    }  
}  

       2.均有环的情况下，判断是否相交

       思路与无环时的思路较类似，二者均有环，那么可以找出各自环的入口点，然后从各自的入口点出发，一个快速（每次2步），一个慢速（每次1步），直到相遇，说明相交。

相关参考博客：

http://blog.csdn.net/yx0628/article/details/24454693

http://wuchong.me/blog/2014/03/25/interview-link-questions/

http://www.jianshu.com/p/c65d9d753c31

http://www.cnblogs.com/smyhvae/p/4782595.html