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.
解题思路：
先遍历两个list的长度，然后长的减去短的，之后同时遍历即可，JAVA实现如下：
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA==null||headB==null)
return null;
int lengthA=0,lengthB=0;
ListNode tempA=headA,tempB=headB;
while(tempA!=null){
tempA=tempA.next;
lengthA++;
}
while(tempB!=null){
tempB=tempB.next;
lengthB++;
}
if(lengthB>lengthA){
tempA=headA;
headA=headB;
headB=tempA;
int temp=lengthA;
lengthA=lengthB;
lengthB=temp;
}
int length=lengthA-lengthB;
while(length-->0)
headA=headA.next;
while(headA!=null){
if(headA==headB)
return headA;
headA=headA.next;
headB=headB.next;
}
return headA;
}