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

- 日理万妓 2023-10-04 17:38 25阅读 0赞

### 描述 ###

输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

数据范围： n \\le 1000n≤1000  
要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

例如，输入\{1,2,3\},\{4,5\},\{6,7\}时，两个无环的单向链表的结构如下图所示：

![cbf36146327bb38a2fb407ed351bf1c6.png][]

可以看到它们的第一个公共结点的结点值为6，所以返回结点值为6的结点。

#### 输入描述： ####

输入分为是3段，第一段是第一个链表的非公共部分，第二段是第二个链表的非公共部分，第三段是第一个链表和第二个链表的公共部分。 后台会将这3个参数组装为两个链表，并将这两个链表对应的头节点传入到函数FindFirstCommonNode里面，用户得到的输入只有pHead1和pHead2。

#### 返回值描述： ####

返回传入的pHead1和pHead2的第一个公共结点，后台会打印以该节点为头节点的链表。

### 示例1 ###

输入：

{1,2,3},{4,5},{6,7}

返回值：

{6,7}

说明：

第一个参数{1,2,3}代表是第一个链表非公共部分，第二个参数{4,5}代表是第二个链表非公共部分，最后的{6,7}表示的是2个链表的公共部分
    这3个参数最后在后台会组装成为2个两个无环的单链表，且是有公共节点的

### 示例2 ###

输入：

{1},{2,3},{}

返回值：

{}

说明：

2个链表没有公共节点 ,返回null，后台打印{}

**方法一：暴力循环**

时间复杂度o(n^2),空间复杂度o(1)

/**
     * struct ListNode {
     *	int val;
     *	struct ListNode *next;
     * };
     *
     * C语言声明定义全局变量请加上static，防止重复定义
     */
    
    /**
     * 
     * @param pHead1 ListNode类 
     * @param pHead2 ListNode类 
     * @return ListNode类
     */
    struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2 ) {
        // write code here
        struct ListNode* p=pHead1,*q=pHead2;
         while(p){
             //struct ListNode* t=q;
             while(q){
                 if(p==q){
                     return p;
                 }
                 q=q->next;
             }
             q=pHead2;
             p=p->next;
         }
         return NULL;
    }

方法二.

设置两个指针，同时遍历两个链表，假设当其中一个链表遍历到末尾时，就重新回到头部，继续

遍历，如果有相同的节点（即使两个链表都遍历到null），两个链表总会有相遇的时刻，则这时的节点就是两个的共同节点。

/**
     * struct ListNode {
     *	int val;
     *	struct ListNode *next;
     * };
     *
     * C语言声明定义全局变量请加上static，防止重复定义
     */
    
    /**
     * 
     * @param pHead1 ListNode类 
     * @param pHead2 ListNode类 
     * @return ListNode类
     */
    struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2 ) {
        // write code here
        struct ListNode* p=pHead1,*q=pHead2;
    //     while(p){
    //         //struct ListNode* t=q;
    //         while(q){
    //             if(p==q){
    //                 return p;
    //             }
    //             q=q->next;
    //         }
    //         q=pHead2;
    //         p=p->next;
    //     }
    //     return NULL;
        while(p!=q){
            p=p?p->next:pHead1;
            q=q?q->next:pHead2;
        }
        return p;
    }

[cbf36146327bb38a2fb407ed351bf1c6.png]: https://img-blog.csdnimg.cn/img_convert/cbf36146327bb38a2fb407ed351bf1c6.png