160.相交链表

160.相交链表

题目描述：

给出两个单链表头结点，长度分别为 $ m,n $ ，返回找到的相交点。如果不相交，返回null。

数据范围：
$ 1\le m, n\le 3\times10^4 $

题解：

直接使用双指针，假设两链表独立部分的长度为 $ a,b $ ,公共部分长度为 $ c $ ，则使用双指针，一个从 headA 开始，一个从headB开始，走到终点就回到另一条链表的头开始遍历。这样的话，第一次相交就是交点。 $ a+c+b = b + c + a $ .

相似的还有一道题目 剑指 Offer II 022. 链表中环的入口节点。这个题目是使用快慢指针，gang shen讲过。

代码：

class Solution
{
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
    {
        ListNode *p1 = headA, *p2 = headB;
        if(p1 == nullptr || p2==nullptr) return nullptr;
        while (p1 != p2)
        {
            if (p1 == nullptr)
                p1 = headB;
            else
                p1 = p1->next;
            // p2 = p2->next;
            if(p2 == nullptr)    
                p2 = headA;
            else 
            	p2 = p2->next;
        }
        return p1;
    }
};