【微软面试一百题：7】判断两个链表是否相交

给出两个单向链表的头指针,比如 h1,h2,判断这俩个链表是否相交。

首先考虑是否存在环

用两个指针p1,p2同时指向链表的头部，p1一次移动一步，p2一次移动两步，如果最终p1和p2重合则说明链表有环，如果p2走到空指针（链表的结尾）则说明链表无环； 如果最终p1和p2重合，使p2重新指向链表的头结点，然后p1和p2同时一次移动一步，当p1和p2再次重合时该节点指针就是环的 -入口节点指针

（1）当fast与slow相遇时，show肯定没有走完链表，而fast已经在还里走了n（n>= 1）圈。假设slow走了s步，那么fast走了2s步。fast的步数还等于s走的加上环里转的n圈，所以有：
2s = s + nr。因此，s = nr。
（2）设整个链表长为L，入口据相遇点X，起点到入口的距离为a。因为slow指针并没有走完一圈，所以：
a + x = s，带入第一步的结果，有：a + x = nr = (n-1)r + r = (n-1)r + L - a；即：
a = (n-1)r + L -a -x;
这说明：从头结点到入口的距离，等于转了(n-1)圈以后，相遇点到入口的距离。因此，我们可以在链表头、相遇点各设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。
以上证明参考 http://blog.csdn.net/thefutureisour/article/details/8174313

struct Node {
    int data;
    int Node *next; 
};
// if there is no cycle.
int isJoinedSimple(Node * h1, Node * h2) {
    while (h1->next != NULL) {
        h1 = h1->next;
    }
    while (h2->next != NULL) {
        h2 = h2-> next;
    }
    return h1 == h2;
}
// if there could exist cycle
int isJoined(Node *h1, Node * h2)
{
    Node* cylic1 = testCylic(h1);
    Node* cylic2 = testCylic(h2);
 // h1 和 h2 都没有环
    if (cylic1+cylic2==0)
        return isJoinedSimple(h1, h2);
//h1 、h2其中有一个存在环，则没有交点
    if (cylic1==0 && cylic2!=0 || cylic1!=0 &&cylic2==0)
        return 0;
    Node *p = cylic1;
    while (1) {
        if (p==cylic2 || p->next == cylic2) return 1;
        p=p->next->next;
        cylic1 = cylic1->next;
        if (p==cylic1) return 0;
    }
}
//判断是否存在环
Node* testCylic(Node * h1) {
    Node * p1 = h1, *p2 = h1;
    while (p2!=NULL && p2->next!=NULL) {
        p1 = p1->next;
        p2 = p2->next->next;
        if (p1 == p2) {
            //返回相遇结点
            return p1;
        }
    }
    return NULL;
}