AcWing 66 两个链表的第一个公共结点
发布日期:2021-05-28 16:30:53 浏览次数:9 分类:技术文章

本文共 871 字,大约阅读时间需要 2 分钟。

题目描述:‘

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

当不存在公共节点时,返回空节点。

样例

给出两个链表如下所示:A:        a1 → a2                   ↘                     c1 → c2 → c3                   ↗            B:     b1 → b2 → b3输出第一个公共节点c1

分析:

本题与有点类似,不过更为简单。设上图中a1到c1的长度为x,b1到c1的长度为y,c1到c3的长度为z,则令p指向第一个链表头结点,q指向第二个链表头结点,p,q逐渐右移,当p到达链表结尾时,从第二个链表起点开始继续遍历;同样的q到达末尾时从第一个链表头结点开始遍历,于是某时刻p,q必然会相遇于c1点(若有公共结点)。此时p移动的距离为x+z+y,q移动的距离为y+z+x。如果没有公共结点,则二者会相遇于末节点的后一个节点,也就是空节点。

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {        auto p = headA,q = headB;        while(p != q){            if(p)  p = p->next;            else    p = headB;            if(q)  q = q->next;            else    q = headA;        }        return p;    }};

 

转载地址:https://blog.csdn.net/qq_30277239/article/details/88547410 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:AcWing 67 数字在排序数组中出现的次数
下一篇:AcWing 65 数组中的逆序对

发表评论

最新留言

很好
[***.229.124.182]2024年02月01日 15时31分43秒