[数据结构与算法]Leetcode160.相交链表（哈希集合/双指针，C++）

*此题借鉴Leetcode官方题解

题目描述：

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

思路1：哈希集合——首先我们可以想到，如果我们把链表A存到数组里面，再对B进行遍历，同时与数组对比，即可完成提议，但是时间复杂度为O(n*n)；过于复杂，优化一下，我们可以考虑用哈希集合（相关内容可以参考(3条消息) 【数据结构与算法】初入数据结构的哈希表(Hash Table)_长路漫漫的歇脚处-CSDN博客），利用哈希集合我们可以把时间复杂度优化到O(m+n)，空间复杂度为O(m);

思路2：双指针——先分别用两个指针遍历链表，当其中一个指针遍历到链表末端时，将其指向另一个链表的头指针，以此继续遍历，直到两个指针指向同一结点或者空指针。

附Leetcode地址：相交链表 - 相交链表 - 力扣（LeetCode） (leetcode-cn.com)

官方题解十分详细，本题解仅用于记录自己的刷题思路，建议参照官方题解。

附代码：

?

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