判断两个链表是否相交并找出交点-笔记

红太狼 2022-07-27 11:54 196阅读 0赞

**本文声明：**  
本文内容并非全部为原创，添加个人想法仅做笔记之用。

判断两个链表是否相交的方法  
**相交链表的特征**：如果两个链表相交，那么交点以后的节点都相同，否则不相交。

![这里写图片描述][20160412214938434]

# 1 暴力搜索法 #

这个地球人都懂得

# 2 节点hash法 #

**两个链表的节点进行hash，然后判断节点hash值和节点的值是否相等来判断。**  
不推荐这样做，每个节点进行hash，然后判断，程序上比较累赘。若要实现，可以参考Java中HashMap的源码实现。

# 3 链表衔接法 #

**一个链表的尾部连接下一个链表的头部，通过判断新链表是否有环**  
这个想法另类，但易于实现，可以参考[单链表存在环的问题][Link 1]

# 4 相交链表的特征法 #

由相交链表的特征可知，每个链表都遍历到最后一个节点，如果最后一个节点相同，则链表相交，否则不相交。一个链表的长度len1，另一个链表的长度len2，那么两个链表只差为|len1-len2|，两个链表的中较长链表在遍历|len1-len2|与较短链表同时遍历,就能找到交点。  
**为什么判断最后一个节点？**  
因为最后一个节点是确定的，而且只需遍历链表即可。

node * findIntersection(node* header1, node* header2) {
        node *p1 = header1;
        node *p2 = header2;
        int len1 = 0, len2 =0;
        if (p1 == NULL || p2 == NULL)
            return NULL;
    
        while (p1->next != NULL) {
            len1++;
            p1 = p1->next;
        }
        while (p2->next != NULL) {
            len2++;
            p2 = p2->next;
        }
    
        int dif = abs(len1, len2);
        int len = 0;
        if (len1 >= len2) {
            p1 = header1;
            p2 = header2;
        }
        if (len2 > len1) {
            p1 = header2;
            p2 = header1;
        }
    
        while (p1->next != NULL && dif > 0) {
            p1 = p1->next;
            dif--;
        }
    
        // 同时遍历，注意：这里直接判断p1 和 p2是否相等，是因为较短链表的头结点可能就是交点
        while (p1 != p2) {
            p1 = p1->next
            p2 = p2->next;
        }
        return p1;
    }

# 参考 #

[判断两个链表是否相交并找出交点][Link 2]

[20160412214938434]: /images/20220724/ebedf6005e8745deb2115a7b8735e696.png
[Link 1]: http://blog.csdn.net/renwotao2009/article/details/51094777
[Link 2]: http://blog.csdn.net/jiqiren007/article/details/6572685