链表相交问题

题目:

给定两个单向链表的头结点指针，比如为h1和h2，判断这两个链表是否相交。

分析：

一、先来分析链表不存在环的情况。

编程之美和JULY的博文闲话链表追赶问题上对该题都有详述，拿来用了。

1.直接循环判断第一个链表的每个节点是否在第二个链表中。但，这种方法的时间复杂度为O(Length(h1) * Length(h2))。显然，我们得找到一种更为有效的方法，至少不能是O（N^2）的复杂度。

2.针对第一个链表直接构造hash表，然后查询hash表，判断第二个链表的每个结点是否在hash表出现，如果所有的第二个链表的结点都能在hash表中找到，即说明第二个链表与第一个链表有相同的结点。时间复杂度为为线性：O(Length(h1) + Length(h2))，同时为了存储第一个链表的所有节点，空间复杂度为O(Length(h1))。是否还有更好的方法呢，既能够以线性时间复杂度解决问题，又能减少存储空间？

3.进一步考虑“如果两个没有环的链表相交于某一节点，那么在这个节点之后的所有节点都是两个链表共有的”这个特点，我们可以知道，如果它们相交，则最后一个节点一定是共有的。而我们很容易能得到链表的最后一个节点，所以这成了我们简化解法的一个主要突破口。那么，我们只要判断俩个链表的尾指针是否相等。相等，则链表相交；否则，链表不相交。
所以，先遍历第一个链表，记住最后一个节点。然后遍历第二个链表，到最后一个节点时和第一个链表的最后一个节点做比较，如果相同，则相交，否则，不相交。这样我们就得到了一个时间复杂度，它为O((Length(h1) + Length(h2))，而且只用了一个额外的指针来存储最后一个节点。这个方法时间复杂度为线性O（N），空间复杂度为O（1），显然比解法2胜一筹。

第3种解法代码如下：

bool intersect(struct node *list1, struct node *list2)
{
    assert(list1 != NULL && list2 != NULL); 
    while (list1->next != NULL) { //遍历list1到末尾
        list1 = list1->next;
    }
    while (list2->next != NULL){ //遍历list2到末尾
        list2 = list2->next;
    }
    if (list1 == list2)
        return true;
    return false;
}

扩展问题：判断两个单链表是否相交，如果相交，给出相交的第一个点（两个链表都不存在环）。
比较好的方法有两个：
1、将其中一个链表首尾相连，检测另外一个链表是否存在环，如果存在，则两个链表相交，而检测出来的依赖环入口即为相交的第一个点。

2、如果两个链表相交，那个两个链表从相交点到链表结束都是相同的节点，我们可以先遍历一个链表，直到尾部，再遍历另外一个链表，如果也可以走到同样的结尾点，则两个链表相交。
这时我们记下两个链表length，再遍历一次，长链表节点先出发前进(lengthMax-lengthMin)步，之后两个链表同时前进，每次一步，相遇的第一点即为两个链表相交的第一个点。

二、如果链表存在环，判断链表相交会更复杂。

2.1）首先解决判断链表是否存在环的问题。

最自然的想法是存储访问过的结点，然后在访问后续结点时与已经访问过的结点比较是否已经存在，时间复杂度为O(N^2)，空间复杂度为O(N)，当然用哈希表存储可以将时间复杂度降至O(N)。使用哈希表的方法代码如下：

bool hasLoop(struct node *head)
{
    map<struct node *, int> m;
    struct node *current = head;
    while (current != NULL) {
        if (m.find(current) == m.end()) {
            m[current] = 1;
            current = current->next;
        }
        else
            return true;
    }
    return false;
}

网上一个广为流传的方法就是快慢指针法，设定快慢两个指针fast，slow，快指针一次走2步，慢指针一次走1步，如果快慢指针能够相遇，则链表存在环，否则不存在环。因为如果链表中存在环，快指针fast必定先入环，慢指针slow后入环，两个指针必然相遇。（如果快指针先到达尾部为NULL，则不存在环）。代码如下：

bool hasLoop(struct node *head)
{
    struct node *fast = head, *slow = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
            return true;
    }
    return false;
}

此外还有一种方法可以判断链表中是否有环，可以将链表逆序，如果有环的话链表最终会返回到头结点。链表逆序算法请参见博文：链表逆序

扩展问题：判断链表有环后，如何确定环的入口点？

当fast若与slow相遇时，slow肯定没有走遍历完链表，而fast已经在环内循环了n圈(n>=1)。假设slow走了s步，则fast走了2s步（fast步数还等于s 加上在环上多转的n圈），设环长为r，则：
2s = s + nr
s= nr
设整个链表长L，入口环与相遇点距离为x，起点到环入口点的距离为a。
a + x = nr
a + x = (n – 1)r +r = (n-1)r + L - a
a = (n-1)r + (L – a – x)
(L – a – x)为相遇点到环入口点的距离，由此可知，从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点，于是我们从链表头、与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。(注意，如果是一个走3步，一个走1步，则不一定相遇，可以由公式推导出)代码如下：

struct node *findLoopPoint(struct node *head)
{
    struct node *fast = head, *slow = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)  //有环
            break;
    }
    if (fast==NULL || fast->next==NULL) //无环返回NULL
        return NULL;
    slow = head;
    while (slow != fast) { //slow指向链表头，fast指向相遇点，两个指针每次走一步必然相遇
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

2.2 ）链表相交问题最终版本

稍微修改下判断链表是否有环的程序hasLoop，便于处理。主要是多加一个变量cycleNode，用于存储环中的一个结点，然后判断该结点是否在另一个链表的环中。修改版本如下：

bool hasLoopExt(struct node *head, struct node * &loopNode)
{
    struct node *fast = head, *slow = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            loopNode = fast; 
           return true;
        }
   }
    return false;
}

最终版本分如下几种情况判断：

1）如果都不存在环，则使用前面的代码判断尾结点是否相等即可；

2）如果一个存在环，另一个不存在环，则这两个链表是不可能相交的；

3）如果都存在环，判断一链表上俩指针相遇的那个节点，在不在另一条链表上。如果在，则相交，如果不在，则不相交。

bool detect(struct node *head1, struct node *head2)
{
 struct node* loopNode1;
 struct node* loopNode2;

 bool hasLoop1 = hasLoopExt(head1,loopNode1);
 bool hasLoop2 = hasLoopExt(head2,loopNode2);

 //一个有环，一个无环 
 if(hasLoop1 != hasLoop2){
 cout << "one cycle, one not" << endl;
 return false;
 }
 //两个都无环，是基本情况，调用最基本的函数即可 
 else if(!hasLoop1 && !hasLoop2)
 {
 return intersect(head1, head2);
 }
 //两个都有环，判断环里的节点是否能到达另一个链表环里的节点 
 else
 {
 cout << "two cycle" << endl;
 struct node* temp = loopNode1->next; 
 while(temp != loopNode1)
 {
 if(temp == loopNode2)
 return true;
 temp = temp->next;
 }
 return loopNode1==loopNode2; //注意这一步，不能漏掉loopNode1的判断，因为我们开始是从loopNode1->next开始比较的
 }
 return false;
}

参考资料

http://blog.csdn.net/v_JULY_v/article/details/6447013

http://www.cppblog.com/humanchao/archive/2008/04/17/47357.html