判断两个链表是否相交 用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;  // 链表没有相交
}