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

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

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

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode p1 = pHead1, p2 = pHead2;
        while (p1 != p2) {
            p1 = (p1 != null) ? p1.next : pHead2;
            p2 = (p2 != null) ? p2.next : pHead1;
        }
        return p1;
    }
}

算法思路:

定义两个指针 p1 和 p2,分别指向两个链表的头节点,然后让它们同时遍历两个链表。当 p1 遍历完当前链表时,将 p1 指向另一个链表的头节点,继续遍历;当 p2 遍历完当前链表时,将 p2 指向另一个链表的头节点,继续遍历。当 p1 和 p2 相遇时,即为它们的第一个公共节点。

为什么这个算法可行呢?假设两个链表的长度分别为 a 和 b,它们的公共部分长度为 c,则有以下三种情况:

  1. a = b,p1 和 p2 遍历完自己的链表后同时到达链表尾部,即 p1 == p2 == null,此时返回 null。
  2. a < b,p1 先到达链表尾部,此时将 p1 指向另一个链表的头节点,即指向长度为 b 的链表的头节点,继续遍历。p2 继续遍历自己的链表,当 p2 到达链表尾部时,将 p2 指向另一个链表的头节点,即指向长度为 a 的链表的头节点,继续遍历。由于 p1 多走了 b - a 步,p2 多走了 a - b 步,因此此时 p1 和 p2 距离公共节点的长度相等,同时移动,必定会在公共节点处相遇。
  3. a > b,同 2,只是 p2 先到达链表尾部,p1 后到达,然后继续遍历,最终也会在公共节点处相遇。

时间复杂度分析:

整个算法只需要遍历每个链表一次,时间复杂度是 O(n)。

空间复杂度分析:

只需要使用常数个额外的指针变量,空间复杂度是 O(1)。

全部评论

相关推荐

但听说转正率很低,我现在有在实习了,好纠结要不要去
熬夜脱发码农:转正率低归低,但是实习的经历你可以拿着,又不是说秋招不准备了
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
06-29 17:30
找实习找着找着就要进入7月了,马上秋招也要开始了,找实习还有意义吗?
绝迹的星:有面就面, 没面上就当日薪4位数大佬免费培训, 面上了再考虑要不要实习
点赞 评论 收藏
分享
叶扰云倾:进度更新,现在阿里云面完3面了,感觉3面答得还行,基本都答上了,自己熟悉的地方也说的比较细致,但感觉面试官有点心不在焉不知道是不是不想要我了,求阿里收留,我直接秒到岗当阿里孝子,学校那边的房子都退租了,下学期都不回学校,全职猛猛实习半年。这种条件还不诱人吗难道 然后现在约到了字节的一面和淘天的复活赛,外加猿辅导。华为笔试完没动静。 美团那边之前投了个base广州的,把我流程卡麻了,应该是不怎么招人,我直接简历挂了,现在进了一个正常的后端流程,还在筛选,不知道还有没有hc。
点赞 评论 收藏
分享
认真搞学习:这么良心的老板真少见
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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