本文共 1954 字，大约阅读时间需要 6 分钟。

判断两个单向链表是否相交，有两种情况，一种是两个不带环的单向链表相交，一种是两个带环的单向链表相交。

情况1：两个不带环的单向链表相交

/*判断两个不带环的单向链表是否相交。时间复杂度O(n)，空间复杂度O(1)*//*思路：如果两个没有环的链表相交于某一节点，那么在这个节点之后的*//*所有节点都是两个链表共有的,如果它们相交，则最后一个节点一定是共有的*/int is_intersect(struct list_head *head_one, struct list_head *head_two){    if (!head_one || !head_two)        return -1;    /*先找到链表1的尾节点*/    while (head_one->next != NULL)        head_one = head_one->next;    /*找链表2的尾节点并比较*/    while (head_two->next != NULL) {        head_two = head_two->next;        /*判断尾节点是否相同*/        if (head_one == head_two)            return 1;/*相交*/    }    return 0;/*相交*/}

情况2：两个带环的单向链表相交

/*判断两个带环的单向链表是否相交*//*思路：如果有环且两个链表相交，则两个链表都有共同一个环，即环上的任意一个节点都存在*//*于两个链表上。因此，就可以判断一链表上俩指针相遇的那个节点，在不在另一条链表上。*/int is_intersect(struct list_head *head_one, struct list_head *head_two){    struct list_head *slow = head_one;    struct list_head *fast = head_one;    struct list_head *temp = NULL;    if (!head_one || !head_one->next ||        !head_two || !head_two->next)        return -1;    /*判断链表1有没有环，并得到链表1的环内节点（两指针相遇的那个节点）*/    while (fast != NULL && fast->next != NULL) {        slow = slow->next;        fast = fast->next->next;        if (slow == fast) {/*有环*/            temp = slow;   /*获取链表1的环内节点*/            break;        }    }    if (slow != fast)/*链表1没有环*/        return -1;    /*判断链表2有没有环*/    slow = head_two;    fast = head_two;    while (fast != NULL && fast->next != NULL) {        slow = slow->next;        fast = fast->next->next;        if (slow == fast)/*有环*/            break;    }    if (slow != fast)/*链表2没有环*/        return -1;    /*这里的slow、fast都为链表2的环内节点，现在遍历这个环，看链表1的环内节点temp在不在这个环上*/    slow = slow->next;    while (slow != fast) {        if (slow == temp)            return 1;/*相交*/        slow = slow->next;    }    return 0;/*不相交*/}

扩展：两链表相交的第一个公共节点

题目描述：如果两个无环单链表相交，怎么求出他们相交的第一个节点呢？

分析：采用对齐的思想。先计算两个链表的长度 L1 , L2，分别用两个指针 p1 , p2 指向两个链表的头，然后将较长链表的 p1（假设为 p1）向后移动L2 - L1个节点，然后再同时向后移动p1 , p2，直到p1 = p2。相遇的点就是相交的第一个节点。

参考博文：

转载地址：http://fdqkb.baihongyu.com/