如何判断两个链表是否相交并找出交点

解题思路

情况1：两个链表均不含有环

1、直接法
采用暴力的方法，遍历两个链表，判断第一个链表的每个结点是否在第二个链表中，时间复杂度为O(len1*len2)，耗时很大。

2、hash计数法
如 果 两个链表相交，则两个链表就会有共同的结点；而结点地址又是结点唯一标识。因而判断两个链表中是否存在地址一致的节点，就可以知道是否相交了。可以对第一 个链表的节点地址进行hash排序，建立hash表，然后针对第二个链表的每个节点的地址查询hash表，如果它在hash表中出现，则说明两个链表有共 同的结点。这个方法的时间复杂度为：O(max(len1+len2)；但同时还得增加O(len1)的存储空间存储哈希表。这样减少了时间复杂度，增加 了存储空间。

以链表节点地址为值，遍历第一个链表，使用Hash保存所有节点地址值，结束条件为到最后一个节点（无环）或Hash中该地址值已经存在（有环）。

再遍历第二个链表，判断节点地址值是否已经存在于上面创建的Hash表中。

这个方面可以解决题目中的所有情况，时间复杂度为O(m+n)，m和n分别是两个链表中节点数量。由于节点地址指针就是一个整型，假设链表都是在堆中动态创建的，可以使用堆的起始地址作为偏移量，以地址减去这个偏移量作为Hash函数

3、转换为环的问题
第三种思路是比较奇特的，在编程之美上看到的。先遍历第一个链表到他的尾部，然后将尾部的next指针指向第二个链表(尾部指针的next本来指向的是null)。这样两个链表就合成了一个链表，判断原来的两个链表是否相交也就转变成了判断新的链表是否有环的问题了：即判断单链表是否有环？

这样进行转换后就可以从链表头部进行判断了，其实并不用。通过简单的了解我们就很容易知道，如果新链表是有环的，那么原来第二个链表的头部一定在环上。因此我们就可以从第二个链表的头部进行遍历的，从而减少了时间复杂度(减少的时间复杂度是第一个链表的长度)。这种方法可以判断两个链表是否相交，但不太容易找出他们的交点。

4、进一步考虑“如果两个没有环的链表相交于某一节点，那么在这个节点之后的所有节点都是两个链表共有的”这个特点，我们可以知道，如果它们相交，则最后一个节点一定是共有的。而我们很容易能得到链表的最后一个节点，所以这成了我们简化解法的一个主要突破口。那么，我们只要判断两个链表的尾指针是否相等。相等，则链表相交；否则，链表不相交。

注意：两个不含环的单链表的相交，相交指的是结点的地址相同，而不是结点的值相同

情况2：链表有环时
1：假设两个链表都有环，情况只有2种
相交于”环上”或相交于”不是环的部分”。因此环一定是在公共部分上的。假如知道其中一个链表上环的任意一个节点，则只需要判断是否在另一个链表上就行了

2：当一个链表中有环，一个链表中没有环时，两个链表必不相交

代码实现

建立在这两篇博客的基础上
1：如何实现链表
2：如何知道链表是否有环

public function detect($linkList1, $linkList2) {
    $p1 = $linkList1->head;
    $p2 = $linkList2->head;

    $size1 = $linkList1->size;
    $size2 = $linkList2->size;

    $isLoop1 = false;
    $isLoop2 = false;
    $circleNode1 = null;
    $circleNode2 = null;

    //此处使用引用
    $linkList1->isLoopLinkListByMap($isLoop1, $circleNode1);
    $linkList2->isLoopLinkListByMap($isLoop2, $circleNode2);

    //一个有环 一个无环
    if($isLoop1 != $isLoop2){
        return false;
    }
    //两个都无环，判断最后一个节点是否相等
    elseif(!$isLoop1 && !$isLoop2){
        for($i = 0; $i< $size1; $i++){
            $p1 = $p1->next;
        }

        for($j = 0; $j< $size2; $j++){
            $p2 = $p2->next;
        }

        if($p1 != $p2){
            return null;
        }
        return true;
    }
    //两个都有环，判断环里的节点是否能到达另一个链表环里的节点 
    else{
        while($circleNode1 != null){
            if($circleNode1 == $circleNode2){
                return true;
            }
            $circleNode1 = $circleNode1->next;
        }
        return false;
    }
    return false;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

扩展知识

求相交的第一个元素

function findNode($linkList1, $linkList2) {
    $p1 = $linkList1->head;
    $p2 = $linkList2->head;
    $diff = 0;
    if($p1 == null || $p2 == null) {
        return null;
    }

    $diff = abs($linkList1->size - $linkList2->size);
    if($linkList1->size > $linkList2->size){
        $p1 = $linkList1->head;
        $p2 = $linkList2->head;
    }
    else {
        $p2 = $linkList1->head;
        $p1 = $linkList2->head;
    }

    for($i = 0; $i < $diff; $i++){
        $p1 = $p1->next;
    }

    while($p1 != null) {
        if($p1 == $p2) {
            return $p1;
        }
        $p1 = $p1->next;
        $p2 = $p2->next;

    }

    return null;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33