160. 相交链表

编写一个程序，找到两个单链表相交的起始节点。
注意：

如果两个链表没有交点，返回 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
    }
};