Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
———A: a1 → a2
—————————c1 → c2 → c3
B: b1 → b2 → b3
begin to intersect at node c1.
Notes:
If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.
這道題有很多種解法，如果不管Note镀梭，有很多解法是比較好想的铅歼，但是只有一種辦法可以滿足上面提出的所有條件母谎。
使用雙指針绞呈，分別從兩個(gè)鏈表的頭開始惶桐，指針到尾部了就定位到另一個(gè)鏈表的頭部襟诸，如果鏈表是相交的绞惦，那么兩個(gè)指針就會(huì)碰見，至于為啥借帘，畫個(gè)鏈表走走就知道了蜘渣。如果兩個(gè)鏈表不相交，那就會(huì)有一個(gè)指針有兩次走到末尾肺然。
var getIntersectionNode = function(headA, headB) {
if (!headA||!headB)
return;
var pointer1 = headA;
var pointer2 = headB;
var flag = 0;
while (pointer1!==pointer2) {
if (!pointer1.next) {
if(flag===2)
return null;
pointer1 = headB;
flag++;
}
else
pointer1 = pointer1.next;
if (!pointer2.next) {
if(flag===2)
return null;
pointer2 = headA;
flag++;
}
else
pointer2 = pointer2.next;
}
return pointer1;
};
