大家好,我是程序员吴师兄,今天给大家图解的题目是 LeetCode 第 160 号问题:相交链表

更多题目图解请访问网站:https://www.algomooc.com

一、题目描述

编写一个程序,找到两个单链表相交的起始节点。

如下面的两个链表

在节点 c1 开始相交。

注意:

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

二、题目解析

为了方便理解,假设链表 A 的节点数为 a,链表 B 的节点数为 b,两链表的公共尾部节点数为 c ,第一个公共节点为 c1

让指针 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

三、动画理解

隐藏内容
本内容需权限查看
  • 普通: 5积分
  • 会员: 免费
  • 算法训练营永久会员: 免费
已有1人解锁查看

四、参考代码

// 登录 https://www.algomooc.com 查看更多图解
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

    // 边界判断
    if (headA == null || headB == null) return null;

    ListNode pA = headA, pB = headBA

    //指针 PA 和 指针 PB 不断向后遍历,直到找到相交点
    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)。

声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。