剑指 Offer 52.两个链表的第一个公共节点

大家好,我是程序员吴师兄,欢迎来到 图解剑指 Offer 结构化专栏,在这个专栏里我将和大家一起学习如何用结构化的思维来思考、解题、写代码,希望能帮助你即使在面试的时候紧张也能做对。

AlgoMooc 算法慕课网,每道题目都有动画和图片,致力于帮助每个程序员通过算法面试!

今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 面试题 52.两个链表的第一个公共节点。

题目汇总链接:https://www.algomooc.com/jianzhioffer

一、题目描述

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

如下面的两个链表

在节点 c1 开始相交。

注意:

  • 如果两个链表没有交点,返回 null。
  • 在返回结果后,两个链表仍须保持原有的结构。
  • 可假定整个链表结构中没有循环。
  • 程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。

二、题目解析

我们依旧用 四步分析法 进行结构化的分析。

  • 模拟:模拟题目的运行。
  • 规律:尝试总结出题目的一般规律和特点。
  • 匹配:找到符合这些特点的数据结构与算法。
  • 边界:考虑特殊情况。

1、模拟

首先假设 A 、B 两个链表是有相交节点的情况。

面试题52. 两个链表的第一个公共节点.002

面试题52. 两个链表的第一个公共节点.003

面试题52. 两个链表的第一个公共节点.004

面试题52. 两个链表的第一个公共节点.005

面试题52. 两个链表的第一个公共节点.006

面试题52. 两个链表的第一个公共节点.007

面试题52. 两个链表的第一个公共节点.008

面试题52. 两个链表的第一个公共节点.009

面试题52. 两个链表的第一个公共节点.010

面试题52. 两个链表的第一个公共节点.011

面试题52. 两个链表的第一个公共节点.012

再假设 A 、B 两个链表是没有相交节点的情况。

面试题52. 两个链表的第一个公共节点.013

面试题52. 两个链表的第一个公共节点.014

面试题52. 两个链表的第一个公共节点.015

面试题52. 两个链表的第一个公共节点.016

2、规律

也就是说,无论 A、B 两个链表是否有相交点,最终都会指向一个相同的节点,要么是它们的公共尾部,要么是 NULL。

让指针 PApB 分别指向链表 A 和链表 B 的头结点,之后两个指针分别以步幅为 1 的速度向链表的尾部遍历。

  • 当指针 pA 遍历到链表 A 的尾节点时,此时指针 pA 走了 a 个节点,将指针 pA 指向链表 B 的头部,继续向后遍历,直至走到 c1,此时指针 PA 总共走了 a + ( b - c ) 步。
  • 当指针 pB 遍历到链表 B 的尾节点时,此时指针 pB 走了 b 个节点,将指针 pB 指向链表 A 的头部,继续向后遍历,直至走到 c1,此时指针 PB 总共走了 b + ( a - c ) 步。

根据数学知识,a + ( b - c ) = b + ( a - c ) ,如果 c > 0,表明两链表有公共尾部, c1 存在,两两链表同时到达 c1;如果 c = 0,表明两链表没有公共尾部,指针 PApB 都指向 NULL

3、匹配

无。

4、边界

  • A 链表为 null
  • B 链表为 null

三、动画描述

隐藏内容

此处内容需要权限查看

  • 普通用户特权:5积分
  • 会员用户特权:免费
  • 算法训练营永久会员用户特权:免费推荐
会员免费查看

四、图片描述

面试题52. 两个链表的第一个公共节点.001

面试题52. 两个链表的第一个公共节点.002

面试题52. 两个链表的第一个公共节点.003

面试题52. 两个链表的第一个公共节点.004

面试题52. 两个链表的第一个公共节点.005

面试题52. 两个链表的第一个公共节点.006

面试题52. 两个链表的第一个公共节点.007

面试题52. 两个链表的第一个公共节点.008

面试题52. 两个链表的第一个公共节点.009

面试题52. 两个链表的第一个公共节点.010

面试题52. 两个链表的第一个公共节点.011

面试题52. 两个链表的第一个公共节点.012

面试题52. 两个链表的第一个公共节点.013

面试题52. 两个链表的第一个公共节点.014

面试题52. 两个链表的第一个公共节点.015

面试题52. 两个链表的第一个公共节点.016

五、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    // 边界判断
    if (headA == null || headB == null) return null;

    // 从两个链表的头结点开始遍历
    ListNode pA = headA, pB = headB;

    //指针 PA 和 指针 PB 不断向后遍历,直到找到相交点
    //如果两个链表不相交,则相当于 null 是它们的相交点,因此不会跳不出 while 循环
    while (pA != pB) {
        // 指针 PA 一开始在链表 A 上遍历,当走到链表 A 的尾部即 null 时,跳转到链表 B 上 
        pA = pA == null ? headB : pA.next;
        // 指针 PB 一开始在链表 B 上遍历,当走到链表 B 的尾部即 null 时,跳转到链表 A 上 
        pB = pB == null ? headA : pB.next;
    }
    return pA;
}
}

六、复杂度分析

时间复杂度

时间复杂度为 O( a + b)。

空间复杂度

空间复杂度为 O(1)。

七、相关标签

  • 链表