public static class Node {  
        public int value;  
        public Node next;  
  
        public Node(int data) {  
            this.value =http://www.mamicode.com/ data;  
        }  
    }  
/*判断是否相交，如果相交，得到第一个相交点*/  
    public static Node getIntersectNode(Node head1, Node head2) {  
        if (head1 == null || head2 == null) {  
            return null;  
        }  
        Node loop1 = getLoopNode(head1);  
        Node loop2 = getLoopNode(head2);  
        if (loop1 == null && loop2 == null) {  
            return noLoop(head1, head2);  
        }  
        if (loop1 != null && loop2 != null) {  
            return bothLoop(head1, loop1, head2, loop2);  
        }  
        return null;  
    }  
/* 
 * 判断是否存在环，如果存在，则找出环的入口点。 
 * 入口点找法：快慢指针，块指针走两步，满指针走一步，如果存在循环，则在慢指针走完环前，总会和快指针相遇。 
 * 从头指针和相遇点同时向后走，相遇的点必定是入口点。*/  
    public static Node getLoopNode(Node head) {  
        if (head == null || head.next == null || head.next.next == null) {  
            return null;  
        }  
        Node n1 = head.next; // n1 -> slow  
        Node n2 = head.next.next; // n2 -> fast  
        while (n1 != n2) {  
            if (n2.next == null || n2.next.next == null) {  
                return null;  
            }  
            n2 = n2.next.next;  
            n1 = n1.next;  
        }  
        n2 = head; // n2 -> walk again from head  
        while (n1 != n2) {  
            n1 = n1.next;  
            n2 = n2.next;  
        }  
        return n1;  
    }  
/*无环时的判断方法*/  
    public static Node noLoop(Node head1, Node head2) {  
        if (head1 == null || head2 == null) {  
            return null;  
        }  
        Node cur1 = head1;  
        Node cur2 = head2;  
        int n = 0;  
        while (cur1.next != null) {  
            n++;  
            cur1 = cur1.next;  
        }  
        while (cur2.next != null) {  
            n--;  
            cur2 = cur2.next;  
        }  
        if (cur1 != cur2) {  
            return null;  
        }  
        cur1 = n > 0 ? head1 : head2;  
        cur2 = cur1 == head1 ? head2 : head1;  
        n = Math.abs(n);  
        while (n != 0) {  
            n--;  
            cur1 = cur1.next;  
        }  
        while (cur1 != cur2) {  
            cur1 = cur1.next;  
            cur2 = cur2.next;  
        }  
        return cur1;  
    }  
/*有环时的判断方法*/  
[java] view plain copy
public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {  
        Node cur1 = null;  
        Node cur2 = null;  
        if (loop1 == loop2) {  
            cur1 = head1;  
            cur2 = head2;  
            int n = 0;  
            while (cur1 != loop1) {  
                n++;  
                cur1 = cur1.next;  
            }  
            while (cur2 != loop2) {  
                n--;  
                cur2 = cur2.next;  
            }  
            cur1 = n > 0 ? head1 : head2;  
            cur2 = cur1 == head1 ? head2 : head1;  
            n = Math.abs(n);  
            while (n != 0) {  
                n--;  
                cur1 = cur1.next;  
            }  
            while (cur1 != cur2) {  
                cur1 = cur1.next;  
                cur2 = cur2.next;  
            }  
            return cur1;  
        } else {  
            cur1 = loop1.next;  
            while (cur1 != loop1) {  
                if (cur1 == loop2) {  
                    return loop1;  
                }  
                cur1 = cur1.next;  
            }  
            return null;  
        }  
    }