题目
编写一个程序，找到两个单链表相交的起始节点。
如下面的两个链表： A: a1 -> a2 -> c1 -> c2 -> c3 B: b1 -> b2 -> b3 -> c1 -> c2 -> c3
在节点 c1 开始相交。
示例 1：
A: 4 -> 1 -> 8 -> 4 -> 5
B: 5 -> 0 -> 1 -> 8 -> 4 -> 5
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：
A: 0 -> 9 -> 1 -> 2 -> 4
B: 3 -> 2 -> 4
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
A: 2 -> 6 -> 4
B: 1 -> 5
输入：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。
注意：
- 如果两个链表没有交点，返回 null.
- 在返回结果后，两个链表仍须保持原有的结构。
- 可假定整个链表结构中没有循环。
- 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
JS实现
1、哈希表法
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} headA
* @param {ListNode} headB
* @return {ListNode}
*/
var getIntersectionNode = function (headA, headB) {
let current = headA;
const map = new Map();
while (current != null) {
map.set(current, true);
current = current.next;
}
current = headB;
while (current != null) {
if (map.has(current)) {
return current;
}
current = current.next;
}
return null;
};
2、双指针法
-
创建两个指针 pA 和 pB，分别初始化为链表 A 和 B 的头结点。然后让它们向后逐结点遍历。
-
当 pA 到达链表的尾部时，将它重定位到链表 B 的头结点 (你没看错，就是链表 B); 类似的，当 pB 到达链表的尾部时，将它重定位到链表 A 的头结点。
-
若在某一时刻 pA 和 pB 相遇，则 pA/pB 为相交结点。
-
想弄清楚为什么这样可行, 可以考虑以下两个链表: A={1,3,5,7,9,11} 和 B={2,4,9,11}，相交于结点 9。 由于 B.length (=4) < A.length (=6)，pB 比 pA 少经过 2 个结点，会先到达尾部。将 pB 重定向到 A 的头结点，pA 重定向到 B 的头结点后，pB 要比 pA 多走 2 个结点。因此，它们会同时到达交点。 如果两个链表存在相交，它们末尾的结点必然相同。因此当 pA/pB 到达链表结尾时，记录下链表 A/B 对应的元素。若最后元素不相同，则两个链表不相交。
作者：LeetCode 链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/xiang-jiao-lian-biao-by-leetcode/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
var getIntersectionNode = function(headA, headB) {
if(headA === null || headB === null){
return null;
}
let head1 = headA;
let head2 = headB;
while(head1 != head2){
if(head1 != null){
head1 = head1.next;
} else {
head1 = headB;
}
if(head2 != null){
head2 = head2.next;
} else {
head2 = headA;
}
}
return head1;
};
测试数据：
//list1: 4,1,8,4,5,
//list2: 5,0,1,8,4,5,
//head1: 4,1,8,4,5|5,0,1,8,4,5,
//head2: 5,0,1,8,4,5|4,1,8,4,5,
function ListNode(val) {
this.val = val;
this.next = null;
}
//链表1： 4,1,8,4,5
var node11 = new ListNode(4);
var node12 = new ListNode(1);
var node8 = new ListNode(8);
var node4 = new ListNode(4);
var node5 = new ListNode(5);
node11.next = node12;
node12.next = node8;
node8.next = node4;
node4.next = node5;
//链表2： 5,0,1,8,4,5
var node21 = new ListNode(5);
var node22 = new ListNode(0);
var node23 = new ListNode(1);
node21.next = node22;
node22.next = node23;
node23.next = node8;
node8.next = node4;
node4.next = node5;