给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
哈希解法
js
/**
* 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) {
// hash
let set = new Set();
let cur = headA;
while (cur) {
set.add(cur);
cur = cur.next;
}
cur = headB;
while (cur) {
if (set.has(cur)) return cur;
cur = cur.next;
}
return null;
};
双指针
若相交，链表 A： a+c, 链表 B : b+c. a+c+b+c = b+c+a+c 。则会在公共处 c 起点相遇。若不相交，a +b = b+a 。因此相遇处是 NULL
js
pA:1->2->3->4->5->6->null->9->5->6->null
pB:9->5->6->null->1->2->3->4->5->6->null
js
var getIntersectionNode = function (headA, headB) {
if (!headA || !headB) return null;
let pA = headA,
pB = headB;
while (pA !== pB) {
pA = pA ? pA.next : headB;
pB = pB ? pB.next : headA;
}
\
return pA;
};