| 🚀 算法题 🚀 |
- 🌲 每天打卡一道算法题，既是一个学习过程，又是一个分享的过程😜
- 🌲 提示：本专栏解题 编程语言一律使用 C# 和 Java 两种进行解题
- 🌲 要保持一个每天都在学习的状态，让我们一起努力成为算法大神吧🧐！
- 🌲 今天是力扣算法题持续打卡第42天🎈！
| 🚀 算法题 🚀 |
给你两个单链表的头节点 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 。
判断两个链表是否相交，可以使用哈希集合存储链表节点。
首先遍历链表 headA，并将链表 headA 中的每个节点加入哈希集合中。然后遍历链表 headB，对于遍历到的每个节点，判断该节点是否在哈希集合中：
如果链表 headB 中的所有节点都不在哈希集合中，则两个链表不相交，返回 null。
思路解析
代码：
public class Solution {
public ListNode GetIntersectionNode(ListNode headA, ListNode headB) {
ISet<ListNode> visited = new HashSet<ListNode>();
ListNode temp = headA;
while (temp != null) {
visited.Add(temp);
temp = temp.next;
}
temp = headB;
while (temp != null) {
if (visited.Contains(temp)) {
return temp;
}
temp = temp.next;
}
return null;
}
}
执行结果
通过
执行用时：124 ms，在所有 C# 提交中击败了65.20%的用户
内存消耗：38.5 MB，在所有 C# 提交中击败了15.20%的用户
复杂度分析
时间复杂度：O( m+n ),其中 m 和 n 是分别是链表 headA 和 headB 的长度。需要遍历两个链表各一次。
空间复杂度：O(m)，其中 m 是链表 headA 的长度。需要使用哈希集合存储链表 headA 中的全部节点。
思路解析
判断两个链表是否相交，可以使用哈希集合存储链表节点。
首先遍历链表 headA，并将链表 headA 中的每个节点加入哈希集合中。然后遍历链表 headB，对于遍历到的每个节点，判断该节点是否在哈希集合中：
如果链表 headB 中的所有节点都不在哈希集合中，则两个链表不相交，返回 null。
代码：
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
Set<ListNode> visited = new HashSet<ListNode>();
ListNode temp = headA;
while (temp != null) {
visited.add(temp);
temp = temp.next;
}
temp = headB;
while (temp != null) {
if (visited.contains(temp)) {
return temp;
}
temp = temp.next;
}
return null;
}
}
执行结果
通过
执行用时：7 ms，在所有 Java 提交中击败了22.83%的用户
内存消耗：42.3 MB，在所有 Java 提交中击败了6.96%的用户
复杂度分析
时间复杂度：O( m+n ),其中 m 和 n 是分别是链表 headA 和 headB 的长度。需要遍历两个链表各一次。
空间复杂度：O(m)，其中 m 是链表 headA 的长度。需要使用哈希集合存储链表 headA 中的全部节点。
思路解析
代码：
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;
}
}
执行结果
通过
执行用时：1 ms，在所有 Java 提交中击败了100.00%的用户
内存消耗：41.2 MB，在所有 Java 提交中击败了59.13%的用户
复杂度分析
时间复杂度：O(m+n)
空间复杂度：O(1)
C#和 Java 两种编程语言进行解题联系客服
