本文是力扣 每日一练：每日一练：LeeCode-面试题 02.07. 链表相交 【链表+迭代】 LeeCode-142. 环形链表 II【链表+集合】 学习与理解过程，本文仅做学习之用，对本题感兴趣的小伙伴可以出门左拐 LeeCode-面试题 02.07. 链表相交LeeCode-面试题 02.07. 链表相交 与 LeeCode-142. 环形链表 II
LeeCode-面试题 02.07. 链表相交
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
示例 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 <= m, n <= 3 * 10^41 <= Node.val <= 10^50 <= skipA <= m0 <= skipB <= n- 如果
listA和listB没有交点，intersectVal为0 - 如果
listA和listB有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]
思路
判断两个单链表有没有相交，只需同步遍历两个链表，当其中一个链表遍历到null，再接着遍历另一链表，一直循环遍历，最终node1==node2，即可
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode node1 = headA;
ListNode node2 = headB;
while(node1!=node2){
node1 = node1==null ?headB:node1.next;
node2 = node2==null?headA:node2.next;
}
return node1;
}
}
LeeCode-142. 环形链表 II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
提示：文章来源：https://www.toymoban.com/news/detail-840945.html
- 链表中节点的数目范围在范围
[0, 10^4]内 -10^5 <= Node.val <= 10^5-
pos的值为-1或者链表中的一个有效索引
思路
set集合方法
直接使用 set集合方法，一次遍历即可，当遇到重复出现的元素，使用set集合的contains方法：visited.contains(cur)判断返回即可文章来源地址https://www.toymoban.com/news/detail-840945.html
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode cur = head;
Set<ListNode> visited = new HashSet<>();
while(cur!=null){
if(visited.contains(cur)){
return cur;
}else{
visited.add(cur);
}
cur = cur.next;
}
return null;
}
}
到了这里，关于每日一练：LeeCode-面试题 02.07. 链表相交 【链表+迭代】 LeeCode-142. 环形链表 II【链表+集合】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
