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

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

https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46

struct ListNode *FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    //分别为两个链表分配两个指针来存放头节点;
    struct ListNode *p = pHead1;
    struct ListNode *p = pHead2;
    //设置一个循环判断————直到两个指针中存放的内容完全相同时,即循环结束。
    while(p!=q){
        //第一个链表上的指针顺着链表的方向依次后移直到为空时,将头节点赋给这个指针。
        if(p)
            p = p->next;
        else p = pHead;//这里注意一定要添加else,因为如果不添加程序会依次往后执行导致进入死循环。
        //同理这样判断第二个链表上的指针。
        if(q)
            q = q->next;
        else q = pHead2;
    }
    return p;//这里无论是返回p还是q都可以。
    }
该题利用同步循环移位的方法可以解决,因为如果两个链表长度要么相同,此时两个指针以相同的速度会在一开始就会相遇,路程也是完全相同的。如果两个链表长度不相同,那么一定是前面不同,此时分别进入循环移位状态,当指针移到空时则重新将头节点赋给该指针,依次进行下去直到两者相等时则循环结束,返回该节点。如下表所示最后会在6相遇。
1
4
2 5
3 6
6 7
7 4
1 5
2 6
3 7
6 4
7 5
1 6
2 7
3 4
6 5
7 6
1 7
2 4
3 5
6 6

全部评论

相关推荐

05-26 10:24
门头沟学院 Java
qq乃乃好喝到咩噗茶:其实是对的,线上面试容易被人当野怪刷了
找工作时遇到的神仙HR
点赞 评论 收藏
分享
一表renzha:手写数字识别就是一个作业而已
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 12:04
毕业生招你惹你了,问一个发薪日来一句别看网上乱七八糟的你看哪个工作没有固定发薪日扭头就取消了面试就问了一句公司都是这个态度吗还搞上人身攻击了...
程序员小白条:呃呃呃,都还没面试,我都不会问这么细,何况通不通过,去不去都另说,你没实力和学历的话,在外面就这样,说实话没直接已读不回就不错了,浪费时间基本上
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务