【微软面试一百题: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;
}

你可能感兴趣的