编写一个程序，找到两个单链表相交的起始节点。
注意：
如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *cur1=headA, *cur2=headB;
while (cur1!=cur2){
cur1= cur1?cur1->next:headB;
/*不相等且不为空指向下一个；不相等为空指向b头指针*/
cur2= cur2?cur2->next:headA;
/*不相等且不为空指向下一个；不相等为空指向a头指针*/
}
return cur1;
/*这个思路就是 ListA + ListB = A + intersection + Bb + intersection
ListB + ListA = Bb + intersection + A + intersection
用大A表示ListA里面非共有 Bb表示listB里面非共有的，可以看到在第二个intersection的开头两个链表长度是一样的，必然相等
所以我们可以遍历A再遍历B，另一个遍历B再遍历A，两个指针必定在第二个交集处相遇，没有交集就是空指针
*/
}
};
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *cur1=headA, *cur2=headB;
if (cur1==NULL || cur1==NULL) return NULL;
while (cur1!=cur2){
if (cur1==NULL) cur1=headB;
else cur1=cur1->next;
if (cur2==NULL) cur2=headA;
else cur2=cur2->next;
}
return cur1;
/* a-b和b-a遍历到最后->next都指向尾部指针null，返回null
}
};
