题解：两个链表的第一个公共结点

一时失言乱红尘 2022-05-18 07:21 153阅读 0赞

#### 写在前面 ####

> 剑指offer：两个链表的第一个公共结点

#### 知识点 ####

*  链表处理

#### 要求 ####

> 输入两个链表，找出它们的第一个公共结点。

#### 解法 ####

class Solution {
        
    public:
        ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
            if(!pHead1||!pHead2) return nullptr;
            ListNode* cur1 = pHead1,*cur2 = pHead2;
            while(cur1&&cur2) {
                cur1 = cur1->next;
                cur2 = cur2->next;
            }
            while(cur1) {
                pHead1 = pHead1->next;
                cur1 = cur1->next;
            }
            while(cur2) {
                pHead2 = pHead2->next;
                cur2 = cur2->next;
            }
            while(pHead2&&pHead1) {
                if(pHead2==pHead1)
                    return pHead1;
                pHead1 = pHead1->next;
                pHead2 = pHead2->next;
            }
            return nullptr;
        }
    };

> 分析

设置两个指针分别cur1,cur2，首先同时遍历两个链表当其中一个走到头的时候两个指针同时停下来。这个时候两个指针之间的距离就是两个链表长度差d。再次从头开始遍历两个链表，但是此时刚才没有走到头的链表要先行d步，此时两者再同时向前走，再判断每一步的结点是否相同。

#### 总结 ####

链表的处理涉及多步的指针操作，需要注意边界和空指针。利用头尾相连等等的思路可以解决很多链表问题。

发表评论取消回复

表情：

评论列表（有 0 条评论，153人围观）

还没有评论，来说两句吧...

相关阅读

相关 N36_两个链表的第一个公共结点。

题目描述输入两个链表，找出它们的第一个公共结点。 package new_offer; / 输入两个链表，找出它们的第一个公共结点。

客官°小女子只卖身不卖艺/ 2023年08月17日 17:36/ 0 赞/ 117 阅读

相关剑指offer：两个链表的第一个公共结点输入两个链表，找出它们的第一个公共结点。

输入两个链表，找出它们的第一个公共结点。如果没有公共节点，则输出NULL； struct ListNode { int val; struct L

小鱼儿/ 2022年08月09日 02:17/ 0 赞/ 150 阅读

相关面试题37：两个链表的第一个公共结点

面试题37：两个链表的第一个公共结点题目描述输入两个链表，找出它们的第一个公共结点。代码： package offer;

柔情只为你懂/ 2022年07月12日 09:09/ 0 赞/ 104 阅读

相关剑指offer 两个链表的第一个公共结点

1.题目描述输入两个链表，找出它们的第一个公共结点。 2.分析如果两个链表有公共节点，那么这两条链表从该公共节点开始往后的部分是重合的。方法1：可

左手的ㄟ右手/ 2022年06月15日 01:16/ 0 赞/ 171 阅读

相关算法-寻找两个链表的第一个公共结点

题目：输入两个链表，找到他们的第一个公共结点，链表结点定义如下： struct ListNode { int value; Li

淩亂°似流年/ 2022年06月09日 22:37/ 0 赞/ 181 阅读

相关题解：两个链表的第一个公共结点

写在前面 > 剑指offer：两个链表的第一个公共结点知识点链表处理要求 > 输入两个链表，找出它们的第一个公共结点。解法

一时失言乱红尘/ 2022年05月18日 07:21/ 0 赞/ 154 阅读

相关两个链表的第一个公共结点 java

两个链表的第一个公共结点 java 题目描述输入两个链表，找出它们的第一个公共结点。 > 代码1： public class Solution {

旧城等待，/ 2022年05月15日 15:27/ 0 赞/ 153 阅读

相关两个链表的第一个公共结点 java

两个链表的第一个公共结点 java 题目描述输入两个链表，找出它们的第一个公共结点。 > 代码1： public class Solution {

骑猪看日落/ 2022年05月13日 19:48/ 0 赞/ 150 阅读

相关【剑指Offer】（链表）两个链表的第一个公共结点

题目链接：[https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46?tpId=13&tqId=11

分手后的思念是犯贱/ 2022年03月17日 14:22/ 0 赞/ 184 阅读

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

时间限制：1秒空间限制：32768K 热度指数：174214 本题知识点： [链表][Link 1] [ 算法知识视频讲解][Link 2] 题目描述输入两个链

朴灿烈づ我的快乐病毒、/ 2022年03月08日 01:40/ 0 赞/ 199 阅读