160.相交链表
16.1 题目
给你两个单链表的头节点 headA 和 headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null。
图示两个链表在节点 c1 开始相交：
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：
输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2。从各自的表头开始算起，链表 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
解释：这两个链表不相交，因此返回 null。
提示：
listA中节点数目为mlistB中节点数目为n1 <= m, n <= 3 * 10^41 <= Node.val <= 10^50 <= skipA <= m0 <= skipB <= n- 如果
listA和listB没有交点，intersectVal为 0 - 如果
listA和listB有交点，intersectVal == listA[skipA] == listB[skipB]
进阶：
你能否设计一个时间复杂度 O(m + n)、仅用 O(1) 内存的解决方案？
16.2 题解
哈希集合
// 方法一：哈希集合
// 使用哈希集合记录链表A的节点，然后遍历链表B，找到第一个在哈希集合中出现的节点即为相交节点
static ListNode GetIntersectionNode1(ListNode headA, ListNode headB)
{
// 创建哈希集合用于记录链表A的节点
HashSet<ListNode> set = new HashSet<ListNode>();
// 将链表A的节点添加到哈希集合中
while (headA != null)
{
set.Add(headA);
headA = headA.next;
}
// 遍历链表B，找到第一个在哈希集合中出现的节点
while (headB != null)
{
// 如果当前节点在哈希集合中出现，则表示找到相交节点，返回该节点
if (set.Contains(headB))
{
return headB;
}
// 否则，继续遍历链表B
headB = headB.next;
}
// 如果遍历完链表B仍未找到相交节点，返回null
return null;
}
双指针
// 方法二：双指针
// 分别使用指针pa和pb遍历链表A和链表B，当某一指针到达链表尾部时，将其指向另一链表的头部，继续遍历。
// 如果存在相交节点，则pa和pb会在相交节点相遇,
// 如果不存在相交节点，则pa和pb都会同时到达链表尾部，最后返回null。
// 双指针走完两个链表的步长都是一样的
// 可以假设A链表长度为m B链表长度为n k是量链表的公共部分
// pa和pb都要走m+n 只是pa先走m在走n pb先走n在走n
// 如果存在相交节点 pa会走到 m+n-k pb会走到n+m-k
//不存在的话k为0 走到末尾了
static ListNode GetIntersectionNode2(ListNode headA, ListNode headB)
{
// 如果链表A或链表B为空，直接返回null，因为不存在相交节点
if (headA == null || headB == null)
{
return null;
}
// 初始化两个指针pa和pb，分别指向链表A和链表B的头部
ListNode pa = headA;
ListNode pb = headB;
// 双指针遍历 如果是没有相交时 两个指针分别遍历两个链表都指向空会跳出循环
while (pa != pb)
{
// 如果当前指针pa不为空，移动到下一节点；否则，移到链表B的头部
pa = (pa != null) ? pa.next : headB;
// 如果当前指针pb不为空，移动到下一节点；否则，移到链表A的头部
pb = (pb != null) ? pb.next : headA;
}
// 返回相交节点或null
return pa;
}
16.3 代码
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
#region 题目
// 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。
// 如果两个链表不存在相交节点，返回 null 。
// 图示两个链表在节点 c1 开始相交：
// 题目数据 保证 整个链式结构中不存在环。
// 注意，函数返回结果后，链表必须 保持其原始结构 。
// 示例 1：
// 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
// 输出：Intersected at '8'
// 解释：相交节点的值为 8。
// 从各自的表头开始算起，链表 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 。
// 从各自的表头开始算起，链表 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。
// 提示：
// listA 中节点数目为 m
// listB 中节点数目为 n
// 1 <= m, n <= 3 * 104
// 1 <= Node.val <= 105
// 0 <= skipA <= m
// 0 <= skipB <= n
// 如果 listA 和 listB 没有交点，intersectVal 为 0
// 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]
// 进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？
#endregion
#region 测试
// 示例 1
int[] listA1 = new int[] { 4, 1, 8, 4, 5 };
int[] listB1 = new int[] { 5, 6, 1, 8, 4, 5 };
int skipA1 = 2;
int skipB1 = 3;
// 使用新的辅助方法生成相交链表
(ListNode headA1_1, ListNode headB1_1) = GenerateIntersectionList(listA1, listB1, skipA1, skipB1);
ListNode result1 = GetIntersectionNode1(headA1_1, headB1_1);
Console.WriteLine($"示例1 方法1 输出：{result1?.val}");
// 示例 1 方法2
(ListNode headA1_2, ListNode headB1_2) = GenerateIntersectionList(listA1, listB1, skipA1, skipB1);
ListNode result1_2 = GetIntersectionNode2(headA1_2, headB1_2);
Console.WriteLine($"示例1 方法2 输出：{result1_2?.val}");
// 示例 2
int[] listA2 = new int[] { 1, 9, 1, 2, 4 };
int[] listB2 = new int[] { 3, 2, 4 };
int skipA2 = 3;
int skipB2 = 1;
// 使用新的辅助方法生成相交链表
(ListNode headA2_1, ListNode headB2_1) = GenerateIntersectionList(listA2, listB2, skipA2, skipB2);
ListNode result2 = GetIntersectionNode1(headA2_1, headB2_1);
Console.WriteLine($"示例2 方法1 输出：{result2?.val}");
// 示例 2 方法2
(ListNode headA2_2, ListNode headB2_2) = GenerateIntersectionList(listA2, listB2, skipA2, skipB2);
ListNode result2_2 = GetIntersectionNode2(headA2_2, headB2_2);
Console.WriteLine($"示例2 方法2 输出：{result2_2?.val}");
// 示例 3
int[] listA3 = new int[] { 2, 6, 4 };
int[] listB3 = new int[] { 1, 5 };
int skipA3 = 3;
int skipB3 = 2;
// 使用新的辅助方法生成相交链表
(ListNode headA3_1, ListNode headB3_1) = GenerateIntersectionList(listA3, listB3, skipA3, skipB3);
ListNode result3 = GetIntersectionNode1(headA3_1, headB3_1);
Console.WriteLine($"示例3 方法1 输出：{result3?.val}");
// 示例 3 方法2
(ListNode headA3_2, ListNode headB3_2) = GenerateIntersectionList(listA3, listB3, skipA3, skipB3);
ListNode result3_2 = GetIntersectionNode2(headA3_2, headB3_2);
Console.WriteLine($"示例3 方法2 输出：{result3_2?.val}");
#endregion
}
#region 答案
// 方法一：哈希集合
// 使用哈希集合记录链表A的节点，然后遍历链表B，找到第一个在哈希集合中出现的节点即为相交节点
static ListNode GetIntersectionNode1(ListNode headA, ListNode headB)
{
// 创建哈希集合用于记录链表A的节点
HashSet<ListNode> set = new HashSet<ListNode>();
// 将链表A的节点添加到哈希集合中
while (headA != null)
{
set.Add(headA);
headA = headA.next;
}
// 遍历链表B，找到第一个在哈希集合中出现的节点
while (headB != null)
{
// 如果当前节点在哈希集合中出现，则表示找到相交节点，返回该节点
if (set.Contains(headB))
{
return headB;
}
// 否则，继续遍历链表B
headB = headB.next;
}
// 如果遍历完链表B仍未找到相交节点，返回null
return null;
}
// 方法二：双指针
// 分别使用指针pa和pb遍历链表A和链表B，当某一指针到达链表尾部时，将其指向另一链表的头部，继续遍历。
// 如果存在相交节点，则pa和pb会在相交节点相遇,
// 如果不存在相交节点，则pa和pb都会同时到达链表尾部，最后返回null。
// 双指针走完两个链表的步长都是一样的
// 可以假设A链表长度为m B链表长度为n k是量链表的公共部分
// pa和pb都要走m+n 只是pa先走m在走n pb先走n在走n
// 如果存在相交节点 pa会走到 m+n-k pb会走到n+m-k
//不存在的话k为0 走到末尾了
static ListNode GetIntersectionNode2(ListNode headA, ListNode headB)
{
// 如果链表A或链表B为空，直接返回null，因为不存在相交节点
if (headA == null || headB == null)
{
return null;
}
// 初始化两个指针pa和pb，分别指向链表A和链表B的头部
ListNode pa = headA;
ListNode pb = headB;
// 双指针遍历 如果是没有相交时 两个指针分别遍历两个链表都指向空会跳出循环
while (pa != pb)
{
// 如果当前指针pa不为空，移动到下一节点；否则，移到链表B的头部
pa = (pa != null) ? pa.next : headB;
// 如果当前指针pb不为空，移动到下一节点；否则，移到链表A的头部
pb = (pb != null) ? pb.next : headA;
}
// 返回相交节点或null
return pa;
}
#endregion
#region 辅助方法
// 定义单链表节点类
public class ListNode
{
public int val;
public ListNode next;
public ListNode(int val = 0, ListNode next = null)
{
this.val = val;
this.next = next;
}
}
// 生成相交链表
static (ListNode headA, ListNode headB) GenerateIntersectionList(int[] valuesA, int[] valuesB, int skipA, int skipB)
{
ListNode headA = GenerateList(valuesA);
ListNode headB = GenerateList(valuesB);
ListNode currentA = headA;
ListNode currentB = headB;
// 移动指针到相交节点之前
for (int i = 0; i < skipA - 1; i++)
{
currentA = currentA.next;
}
for (int i = 0; i < skipB - 1; i++)
{
currentB = currentB.next;
}
// 设置相交节点
currentA.next = currentB.next;
return (headA, headB);
}
// 生成链表
static ListNode GenerateList(int[] values)
{
ListNode head = new ListNode(values[0]);
ListNode current = head;
for (int i = 1; i < values.Length; i++)
{
current.next = new ListNode(values[i]);
current = current.next;
}
return head;
}
#endregion
}
16.4 运行结果
示例1 方法1 输出：8
示例1 方法2 输出：8
示例2 方法1 输出：2
示例2 方法2 输出：2
示例3 方法1 输出：
示例3 方法2 输出：
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com
