请写一个程序，找到两个单链表最开始的交叉节点。
注意事项
如果两个链表没有交叉，返回null。
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
/**
* 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
if (headA == NULL || headB == NULL) {
return NULL;
}
ListNode *orgiHeadA =headA;
ListNode *orgiHeadB =headB;
ListNode *longHead;
ListNode *shortHead;
int longCount ;
int shortCount ;
int countA = 1;
int countB = 1;
while(headA = headA->next) {
countA++;
}
while(headB = headB->next) countB++;
if (countA > countB) {
longCount = countA;
shortCount = countB;
longHead = orgiHeadA;
shortHead = orgiHeadB;
} else {
longCount = countB;
shortCount = countA;
longHead = orgiHeadB;
shortHead = orgiHeadA;
}
int delta = longCount - shortCount;
while(delta) {
longHead = longHead -> next;
delta--;
}
while(longHead) {
if (longHead == shortHead) {
return longHead;
}
longHead = longHead->next;
shortHead = shortHead->next;
}
return NULL;
}
};
http://www.lintcode.com/zh-cn/problem/intersection-of-two-linked-lists/
