什么情况两个链表会相交

两个链表相交指的是它们在某个结点处拥有相同的后继结点，如下图所示：

链表1：A->B->C->D->E
链表2：G->H->C->D->E

在这个例子中，链表1和链表2在结点C处相交，因为它们在结点C之后的所有结点都是相同的。

两个链表相交的情况有以下两种：

1. 两个链表的尾部相同。例如上面的例子，链表1的尾部是结点E，链表2的尾部也是结点E。
2. 两个链表的尾部不相同，但是它们中间的某个结点处拥有相同的后继结点。例如上面的例子，链表1和链表2在结点C处相交。

需要注意的是，两个链表相交并不意味着它们的长度相同，也不意味着它们的起点相同。两个链表相交只是指它们在某个结点处拥有相同的后继结点。

相关问题

判断两个链表是否相交

要判断两个链表是否相交，可以使用以下的方法：

1. 遍历第一个链表，将每个节点的地址存储在一个集合中。
2. 遍历第二个链表，检查每个节点的地址是否在集合中存在。如果存在，则两个链表相交；如果不存在，则两个链表不相交。

这种方法的时间复杂度是O(m+n)，其中m和n分别是两个链表的长度。需要额外的空间来存储节点地址的集合。

另外，如果两个链表相交，它们在相交点之后的节点都是相同的。因此，可以先遍历两个链表，得到它们的长度差diff。然后让较长的链表先走diff步，然后同时遍历两个链表，直到找到相同的节点或者遍历结束。这种方法的时间复杂度为O(max(m,n))，不需要额外的空间。

判断两个链表是否相交 用c

判断两个链表是否相交的问题通常可以使用快慢指针（Floyd算法也称为龟兔赛跑法）来解决。以下是基本的步骤：

1. **创建两个指针**：分别初始化为两个链表的头节点，记为`p1`和`q1`。

2. **设置两个慢速指针**：让它们都向链表的末尾移动，速度分别为每一步走一格（`p1`）和两格（`q1`）。

3. **当一个指针到达链表末尾时**，检查另一个指针的位置。如果`q1`已经到达了`p1`的位置，说明两个链表有交叉点；如果`q1`还没到达`p1`的终点，则将`q1`恢复到初始位置（即从链表的头节点开始），然后让`q1`继续以两步一格的速度前进，同时`p1`保持原地不动。

4. **比较当前指针**：如果`q1`再次追上`p1`，那么它们之前的交叉点就是两个链表相交的地方。如果没有交叉点，就表示这两个链表不相交。

// 假设链表节点结构为 struct ListNode {
//     int val;
//     struct ListNode* next;
// };

struct ListNode* intersect(struct ListNode* p1, struct ListNode* q1) {
    struct ListNode *slow_p = p1, *fast_p = q1;
    while (slow_p && fast_p) {
        if (slow_p->next) {
            slow_p = slow_p->next;
            if (fast_p->next) {
                fast_p = fast_p->next->next;
            } else {
                // 如果 fast_p 的下一个节点为空，说明 q1 已经越过 p1
                fast_p = p1;
            }
        } else {
            // slow_p 走完一圈回到起点，此时与 fast_p 比较
            slow_p = q1;
        }
        if (slow_p == fast_p) {
            return slow_p;
        }
    }
    return NULL;  // 链表没有相交
}