题目描述
给你两个单链表的头节点 headA 和 headB,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null。
题目数据保证整个链式结构中不存在环。
示例 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 个节点。
示例 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 输出:No intersection 解释:由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。这两个链表不相交,因此返回 null。
核心思路
双指针法:两个指针分别从两个链表头开始,走完自己的链表后切换到对方的链表头继续走。
关键认知:如果两个链表相交,两个指针最终会在相交点相遇;如果不相交,最终都会走到 null。
链表 A: a1 → a2 → c1 → c2 → c3
链表 B: b1 → b2 → b3 → c1 → c2 → c3
↑ 相交点
指针 pA 走的路径:a1 → a2 → c1 → c2

