力扣160. 相交链表

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

如下面的两个链表：

在节点 c1 开始相交。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

题解

定义两个指针，分别向尾走

当两个指针走到尾时 就分别走对方的路 所有路程加起来 a+c+b == b+c+a 所以两个节点相交，则两个指针必定在相交节点相遇

 class Solution {
    
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    
        ListNode *A = headA,*B = headB;
        while(A != B)
        {
    
            A = A != nullptr  ? A = A->next : headB;
            B = B != nullptr  ? B = B->next : headA;
        }
        return A;

    }
};

时间复杂度 : O(m+n)。
空间复杂度 : O(1)。