您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

找出两个链表的第一个公共节点

时间:2020-10-19 13:45:15  来源:  作者:

问题描述

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

如下面的两个链表:

462. 找出两个链表的第一个公共节点

 

在节点 c1 开始相交。

 

示例 1:

462. 找出两个链表的第一个公共节点

 

输入:intersectVal = 8,

listA = [4,1,8,4,5],

listB = [5,0,1,8,4,5],

skipA = 2, skipB = 3

 

输出:Reference of the node with value = 8

 

输入解释:相交节点的值为 8 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B
为 [5,0,1,8,4,5]。在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。

 

示例 2:

462. 找出两个链表的第一个公共节点

 

输入:intersectVal = 2,

listA = [0,9,1,2,4],

listB = [3,2,4],

skipA = 3, skipB = 1

 

输出:Reference of the node with value = 2

 

输入解释:相交节点的值为 2 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [0,9,1,2,4],链表 B
为 [3,2,4]。在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。

 

示例 3:

462. 找出两个链表的第一个公共节点

 

输入:intersectVal = 0,

listA = [2,6,4],

listB = [1,5],

skipA = 3, skipB = 2

 

输出:null

 

输入解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。由于这两个链表不相交,所以 intersectVal
必须为 0,而 skipA 和 skipB 可以是任意值。

解释:这两个链表不相交,因此返回 null。

 

注意:

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

 

通过集合set解决

上面说了一大堆,其实就是判断两个链表是否相交,如果相交就返回他们的相交的交点,如果不相交就返回null。

做这题最容易想到的一种解决方式就是先把第一个链表的节点全部存放到集合set中,然后遍历第二个链表的每一个节点,判断在集合set中是否存在,如果存在就直接返回这个存在的结点。如果遍历完了,在集合set中还没找到,说明他们没有相交,直接返回null即可,原理比较简单,直接看下代码

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    //创建集合set
    Set<ListNode> set = new HashSet<>();
    //先把链表A的结点全部存放到集合set中
    while (headA != null) {
        set.add(headA);
        headA = headA.next;
    }

    //然后访问链表B的结点,判断集合中是否包含链表B的结点,如果包含就直接返回
    while (headB != null) {
        if (set.contains(headB))
            return headB;
        headB = headB.next;
    }
    //如果集合set不包含链表B的任何一个结点,说明他们没有交点,直接返回null
    return null;
}
123456789101112131415161718

 

先统计两个链表的长度

还可以先统计两个链表的长度,如果两个链表的长度不一样,就让链表长的先走,直到两个链表长度一样,这个时候两个链表再同时每次往后移一步,看节点是否一样,如果有相等的,说明这个相等的节点就是两链表的交点,否则如果走完了还没有找到相等的节点,说明他们没有交点,直接返回null即可,来画个图看一下。

462. 找出两个链表的第一个公共节点

 

最后再来看下代码

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    //统计链表A和链表B的长度
    int lenA = length(headA), lenB = length(headB);

    //如果节点长度不一样,节点多的先走,直到他们的长度一样为止
    while (lenA != lenB) {
        if (lenA > lenB) {
            //如果链表A长,那么链表A先走
            headA = headA.next;
            lenA--;
        } else {
            //如果链表B长,那么链表B先走
            headB = headB.next;
            lenB--;
        }
    }

    //然后开始比较,如果他俩不相等就一直往下走
    while (headA != headB) {
        headA = headA.next;
        headB = headB.next;
    }
    //走到最后,最终会有两种可能,一种是headA为空,
    //也就是说他们俩不相交。还有一种可能就是headA
    //不为空,也就是说headA就是他们的交点
    return headA;
}

//统计链表的长度
private int length(ListNode node) {
    int length = 0;
    while (node != null) {
        node = node.next;
        length++;
    }
    return length;
}

 

双指针解决

我们还可以使用两个指针,最开始的时候一个指向链表A,一个指向链表B,然后他们每次都要往后移动一位,顺便查看节点是否相等。如果链表A和链表B不相交,基本上没啥可说的,我们这里假设链表A和链表B相交。那么就会有两种情况,

 

一种是链表A的长度和链表B的长度相等,他们每次都走一步,最终在相交点肯定会相遇。

一种是链表A的长度和链表B的长度不相等,如下图所示

462. 找出两个链表的第一个公共节点

 

虽然他们有交点,但他们的长度不一样,所以他们完美的错开了,即使把链表都走完了也找不到相交点。

 

我们仔细看下上面的图,如果A指针把链表A走完了,然后再从链表B开始走到相遇点就相当于把这两个链表的所有节点都走了一遍,同理如果B指针把链表B走完了,然后再从链表A开始一直走到相遇点也相当于把这两个链表的所有节点都走完了

 

所以如果A指针走到链表末尾,下一步就让他从链表B开始。同理如果B指针走到链表末尾,下一步就让他从链表A开始。只要这两个链表相交最终肯定会在相交点相遇,如果不相交,最终他们都会同时走到两个链表的末尾,我们来画个图看一下

462. 找出两个链表的第一个公共节点

 

 

462. 找出两个链表的第一个公共节点

 

如上图所示,A指针和B指针如果一直走下去,那么他们最终会在相交点相遇,最后再来看下代码

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    //tempA和tempB我们可以认为是A,B两个指针
    ListNode tempA = headA;
    ListNode tempB = headB;
    while (tempA != tempB) {
        //如果指针tempA不为空,tempA就往后移一步。
        //如果指针tempA为空,就让指针tempA指向headB(注意这里是headB不是tempB)
        tempA = tempA == null ? headB : tempA.next;
        //指针tempB同上
        tempB = tempB == null ? headA : tempB.next;
    }
    //tempA要么是空,要么是两链表的交点
    return tempA;
}

注意:这里所说的指针并不是C语言中的指针,在这里其实他就是一个变量,千万不要搞混了。

 

问题分析

第一种解法应该是都容易想到的,但效率不高,一个个存储,然后再拿另一个链表的节点一个个判断。最后一种解法没有统计链表的长度,而是当一个链表访问完如果没有找到相交点,就从下一个链表继续访问,一般不太容易想到,也算是比较经典的。



Tags:公共节点   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
问题描述输入两个链表,找出它们的第一个公共节点。如下面的两个链表: 在节点 c1 开始相交。 示例 1: 输入:intersectVal = 8,listA = [4,1,8,4,5],listB = [5,0,1,8,4,5],skipA...【详细内容】
2020-10-19  Tags: 公共节点  点击:(124)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(9)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(19)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(13)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(37)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
相关文章
    无相关信息
最新更新
栏目热门
栏目头条