每日一题-两个链表的第一个公共结点

两个链表的第一个公共结点

问题描述

给定两个无环的单向链表，找到它们的第一个公共节点。如果没有公共节点，则返回空。

要求：

• 空间复杂度： $O(1)$
• 时间复杂度： $O(n)$
• 数据范围： 链表长度 $n\le 1000$

输入数据分为三个部分：

1. 第一个链表的非公共部分。
2. 第二个链表的非公共部分。
3. 两个链表的公共部分。

后台会根据输入组装成两个单链表，传入FindFirstCommonNode函数，返回第一个公共节点。

示例说明

示例 1

输入：
{1,2,3}, {4,5}, {6,7}

链表结构：
第一个链表：1 -> 2 -> 3 -> 6 -> 7
第二个链表：4 -> 5 -> 6 -> 7

输出：
{6,7}

说明：
两个链表从节点值为 6 的位置开始公共，返回节点值为 6 的节点。

示例 2

输入：
{1}, {2,3}, {}

链表结构：
第一个链表：1
第二个链表：2 -> 3

输出：
{}

说明：
两个链表没有公共节点，返回 null。

方法及实现

方法描述

采用双指针法：

1. 设置两个指针 first 和 second 分别指向两个链表的头节点。
2. 当 first 和 second 不相等时，指针逐步向后移动：
   • 如果某个指针到达链表尾部，则跳转到另一个链表的头部。
   • 如果两个指针在某节点相遇，则该节点为第一个公共节点。
   • 如果两指针遍历结束仍未相遇，则无公共节点，返回 NULL。

代码实现

struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2) {
    if (pHead1 == NULL || pHead2 == NULL) {
        return NULL;  // 如果任何一个链表为空，直接返回 NULL
    }

    struct ListNode* first = pHead1;  // 指针 first 初始指向链表1头部
    struct ListNode* second = pHead2;  // 指针 second 初始指向链表2头部

    // 当两个指针不相等时，继续循环
    while (first != second) {
        first = (first != NULL) ? first->next : pHead2;  // 如果 first 到达末尾，跳转到链表2头部
        second = (second != NULL) ? second->next : pHead1;  // 如果 second 到达末尾，跳转到链表1头部
    }

    return first;  // 返回第一个公共节点或 NULL
}

复杂度分析

1. 时间复杂度：

   • 每个指针最多遍历两个链表的长度，总时间复杂度为 $O(n+m)$，其中 $n$ 和 $m$ 分别是两个链表的长度。

2. 空间复杂度：

   • 只使用了两个指针，空间复杂度为 $O(1)$。

示例运行过程

示例 1

输入：{1,2,3}, {4,5}, {6,7}
链表1：1 -> 2 -> 3 -> 6 -> 7
链表2：4 -> 5 -> 6 -> 7

• 初始：first 指向 1，second 指向 4。
• 第一次遍历：first 和 second 分别遍历各自链表，到达尾部后跳转到另一链表头部。
• 第二次遍历：first 和 second 在节点 6 相遇。
• 输出：{6,7}。

示例 2

输入：{1}, {2,3}, {}
链表1：1
链表2：2 -> 3

• 初始：first 指向 1，second 指向 2。
• 第一次遍历：first 遍历到尾部后跳转到链表2头部，second 遍历到尾部后跳转到链表1头部。
• 第二次遍历：first 和 second 均到达尾部（NULL）。
• 输出：{}。

总结

• 双指针法通过交替遍历链表，保证了时间复杂度 $O(n+m)$，且额外空间复杂度为 $O(1)$。
• 代码简单高效，能够准确找到第一个公共节点或判定无公共节点。

备注

最开始我写的代码是这样的

while (first!=second) {
     if(first->nex!=NULL)
    first= first->next;
    else first= pHead2;

     if(second->next!=NULL)
    second= second->next;
    else second= pHead1;
 }

结果发现有问题，如果两个不相交的链表，改成下面的才正确

while (first!=second) {
        if(first->next!=NULL)
       first= first->next;
       else first= pHead2;
 
        if(second->next!=NULL)
       second= second->next;
       else second= pHead1;
    }

思考了下原因，原来是如果按照旧的代码， if(first->next!=NULL)，那么说明当前是队尾，使用 first= first->next;相当于第一个把第二个连起来了，两个队列相互首位相连，原本不
else first= pHead2;