记录每日LeetCode 160.相交链表 Java实现
创始人
2024-05-15 09:07:53
0

题目描述:

给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。

图示两个链表在节点 c1 开始相交:

题目数据 保证 整个链式结构中不存在环。

注意,函数返回结果后,链表必须 保持其原始结构 。

自定义评测:

评测系统 的输入如下(你设计的程序 不适用 此输入):

    intersectVal - 相交的起始节点的值。如果不存在相交节点,这一值为 0
    listA - 第一个链表
    listB - 第二个链表
    skipA - 在 listA 中(从头节点开始)跳到交叉节点的节点数
    skipB - 在 listB 中(从头节点开始)跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构,并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点,那么你的解决方案将被 视作正确答案 。

初始代码:

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {}
}

示例1:

输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出:Intersected at '8'
解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,6,1,8,4,5]。
在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。
— 请注意相交节点的值不为 1,因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说,它们在内存中指向两个不同的位置,而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点,B 中第四个节点) 在内存中指向相同的位置。

示例2:

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

 

示例3:

输入: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 。

参考答案:

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {//只要其中一个链表为空就不可能存在相交元素if(headA == null || headB == null) return null;//定义一个集合用来存放其中一个链表中的元素List list = new LinkedList<>();ListNode temp = headA;//遍历A链表放入集合当中while (temp != null) {list.add(temp);temp = temp.next;}temp = headB;//遍历B链表判断集合中是否有其值while (temp != null) {//如果包含则说明两个链表相交了 直接返回即可if (list.contains(temp)) return temp;temp = temp.next;}return null;}
}
/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {//官方解法双指针if(headA == null || headB == null) return null;ListNode pA = headA, pB = headB;while (pA != pB) {pA = pA == null ? headB : pA.next;pB = pB == null ? headA : pB.next;}return pA;}
}

相关内容

热门资讯

linux运行apk文件-如何... 嘿,大家好!今天咱们聊聊一个挺有趣的话题——Linux系统上跑APK文件。是不是听起来就有点像两个平...
nvvsvc.exe可以禁止吗... 哎呀,说到这个nvvsvc.exe,我这心里就一阵烦躁!你知道吗,每次电脑卡得像老牛拉破车,我就恨不...
考勤管理系统忘记密码-考勤系统... 哎呀呀,今天一大早,阳光明媚,心情本来挺好的,准备打卡上班,结果呢?考勤系统居然不让我进!密码是什么...
sfc.exe-探索电脑世界的... 大家好,我今天要和大家聊聊那个总是在我电脑里默默工作的小家伙——SFC.exe。这个名字听起来是不是...
雨林木风装机版下载:开启电脑全... 大家好,我是你们的老朋友,一个对电脑软件充满无限热情的“技术宅”。今天,我要和大家聊聊那个让我心跳加...
linux打开文件-在 Lin... 哎呀,你们知道吗?我今天简直像发现新大陆一样,竟然学会了在Linux上打开文件!这事儿说起来可能对你...
gps基本原理简述-GPS 原... 嘿,朋友们!今天咱们聊聊那个神奇的GPS,就是那个在手机里帮我们找路的小帮手。你知道它是怎么工作的吗...
帝国模板css文件-帝国模板 ... 嘿,各位设计界的探险家们!今天我要跟你们聊聊我的秘密武器——帝国模板CSS文件!没错,就是这个小小的...
iphone6电池能用多久-手... 哎呀,说到我的小6,那真是一段又爱又恨的回忆啊!你知道吗,当初刚拿到手的时候,那电池简直像是永动机,...
gps工作原理图-GPS:手机... 哟,大家好!今天咱们聊聊那个让咱们不迷路的小帮手——GPS,就是那个在你手机里,随时随地告诉你“前方...
richtextbox 背景-... 嘿,你知道吗?今天我的RichTextBox换上了新背景,简直美翻了!它不再是那个单调的白底黑字,像...
游民星空怎么安装游戏?-游民星... 哟,朋友们!今天咱们聊聊怎么在游民星空这个神奇的地方安装游戏。别担心,这不会是一场枯燥的教程,而是一...
unix网络编程卷一-Unix... 亲爱的读者们,当我提起“Unix网络编程卷一”,你是否也和我一样,心中涌起一股既熟悉又有些悸动的情感...
haiku stairs 机票... 在这篇文章里,我想带你走进一个梦幻般的世界,那里有着蜿蜒曲折的HaikuStairs,就像是一张通往...
呼吸道合胞病毒 hep-呼吸道... 哎呀,说到这个呼吸道合胞病毒,真是让人头疼!这小东西,别看它不起眼,可是能让人咳嗽、打喷嚏,甚至发烧...
金山电池医生旧版:简单实用的手... 嘿,还记得那个陪伴我们无数个日夜的金山电池医生旧版吗?那个简单却无比实用的小工具,曾经是我们手机的贴...
shopnc模板-ShopNC... 大家好呀!今天我想跟大家聊聊我和ShopNC模板的不解之缘。哎呀,这个模板啊,真是让我又爱又恨!一开...
win7如何卸载软件64位-W... 哎呀,说到这个Win764位系统卸载软件,我可是有一肚子的话要说!每次想清理电脑里那些不再用的软件,...
acs.exe停止工作-ACS... 天哪,ACS.exe又停止工作了!这已经是这周第三次了,我的电脑你是要造反吗?每次我正兴致勃勃地打开...
穿越火线登陆不上去-穿越火线服... 哎呀,真是气死我了!今天一整天就指望着玩会儿《穿越火线》放松一下,结果一打开电脑,准备登陆游戏,它居...