*此题借鉴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;}
};