请写一个程序，找到两个单链表最开始的交叉节点。
注意事项
如果两个链表没有交叉，返回null。
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
您在真实的面试中是否遇到过这个题？
Yes
样例
下列两个链表：
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
/**
* @param headA: the first list
* @param headB: the second list
* @return: a ListNode
*/
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
// write your code here
int diff1=0;
int diff2=0;
ListNode * p1=headA;
ListNode * p2=headB;
while(p1!=NULL&&p2!=NULL){
p1=p1->next;
p2=p2->next;
}
if(p1==NULL){
while(p2!=NULL){
diff2++;
p2=p2->next;
}
}
else{
while(p1!=NULL){
diff1++;
p1=p1->next;
}
}
p1=headA;
p2=headB;
if(diff1>0){
//p1 chang
int ret=diff1;
while(ret){
p1=p1->next;
ret--;
}
}
else{
int ret2=diff2;
while(ret2){
p2=p2->next;
ret2--;
}
}
ListNode * same;
while(p1!=p2){
p1=p1->next;
p2=p2->next;
}
same=p1;
return same;
}
};
