【春雷课堂】LeetCode刷题：160. 相交链表
「青少年编程竞赛交流群」已成立（适合6至18周岁的青少年），公众号后台回复【Scratch】或【Python】，即可进入，如果加入了之前的社群不需要重复加入人力资源。进群之后大家可以参与每周日晚20:00的升级打怪活动以及每个月的青少年编程组队学习活动。
「青少年编程竞赛交流群」已成立（适合6至18周岁的青少年），公众号后台回复【Scratch】或【Python】，即可进入，如果加入了之前的社群不需要重复加入人力资源。进群之后大家可以参与每周日晚20:00的升级打怪活动以及每个月的青少年编程组队学习活动。
题目：相交链表
题号：160
难度：简单
/
题号：160
难度：简单
/
题号：160
难度：简单
/
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点人力资源。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
展开全文
题目数据 保证整个链式结构中不存在环人力资源。
注意，函数返回结果后，链表必须 保持其原始结构人力资源。
自定义评测：
评测系统的输入如下（人力资源你设计的程序 不适用此输入）：
intersectVal - 相交的起始节点的值人力资源。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中 （从头节点开始）跳到交叉节点的节点数
intersectVal - 相交的起始节点的值人力资源。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中 （从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序人力资源。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案。
示例 1：
输入：intersectVal = 8, listA = [ 4, 1, 8, 4, 5], listB = [ 5, 0, 1, 8, 4, 5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8（注意，如果两个链表相交则不能为 0）人力资源。
从各自的表头开始算起，链表 A 为 [ 4, 1, 8, 4, 5]，链表 B 为 [ 5, 0, 1, 8, 4, 5]人力资源。
在 A 中，相交节点前有 2个节点；在 B 中，相交节点前有 3个节点人力资源。
示例 2：
输入：intersectVal = 2, listA = [ 0, 9, 1, 2, 4], listB = [ 3, 2, 4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2（注意，如果两个链表相交则不能为 0）人力资源。
从各自的表头开始算起，链表 A 为 [ 0, 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 人力资源。
注意：
listA 中节点数目为 m
listB 中节点数目为 n
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点人力资源， intersectVal 为 0
如果 listA 和 listB 有交点人力资源， intersectVal == listA[skipA] == listB[skipB]
listA 中节点数目为 m
listB 中节点数目为 n
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点人力资源， intersectVal 为 0
如果 listA 和 listB 有交点人力资源， intersectVal == listA[skipA] == listB[skipB]
进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案人力资源？
实现
思路：通过集合的方法
C# 语言
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) { val = x; }
publicclassSolution
publicListNode GetIntersectionNode(ListNode headA, ListNode headB)
HashSet<ListNode> hash = newHashSet<ListNode>;
ListNode temp = headA;
while(temp != null)
hash.Add(temp);
temp = temp.next;
temp = headB;
while(temp != null)
if(hash.Contains(temp))
returntemp;
temp = temp.next;
returnnull;
Python 语言
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
classSolution(object):
defgetIntersectionNode(self, headA, headB):
:type head1, head1: ListNode
:rtype: ListNode
h = set
temp = headA
whiletemp isnotNone:
h.add(temp)
temp = temp.next
temp = headB
whiletemp isnotNone:
iftemp inh:
returntemp
temp = temp.next
returnNone
青少年编程升级打怪计划
把电子学会的青少年编程能力等级测评作为游戏的关卡，带着小朋友们升级打怪人力资源。
每周日晚20:00，利用腾讯会议进行直播分享，之后安排一个测试（与等级测评的题目数量一致）考察小朋友们对知识的掌握情况人力资源。
为了，让各个阶段的小朋友都能参与到学习中，我们每个月都会组织Scratch、Python、C++的青少年编程学习活动，为小朋友们三助力，即学习编程助力、实践知识助力、结识伙伴助力人力资源。
一键三连人力资源，一起学习⬇️
相关文章
发表评论