思路一：哈希表法
把其中一个链表中的值存入哈希表中，然后在这个构建的哈希表中寻找另一链表中的值
/*** 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) {if (headA == NULL || headB == NULL) {return NULL;}//创建一个哈希表用于存储链表headA中的值unordered_set<ListNode*> copy_headA;//声明一个指针ListNode *p = headA;//将headA中的值存入哈希表中while(p != NULL){copy_headA.insert(p);p = p->next;}//在哈希表中寻找headB的值，找到第一个就说明后续全部重合p = headB;while(p != NULL){auto it = copy_headA.find(p);if(it != copy_headA.end()){return p;}p = p->next;}return NULL;}
};看官方题解空值使用的是nullptr，这是相较于NULL更安全的一种空值表示
- 时间复杂度：O(headA.length+headB.length)
- 空间复杂度：O(headA.length)
思路二：双指针法
使用两个指针分别指向两个链表的头部，环状检查是否有重合部分
/*** 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) {if(headA == NULL || headB == NULL){return NULL;}ListNode *p = headA;ListNode *q = headB;while(p != q){p = p == NULL ? headB : p->next;q = q == NULL ? headA : q->next;}return p;}
};当指向headA的指针遍历完headA中的所有节点后指向headB的原因是：
指向headA和headB的指针是同时移动的，如果重合部分之前的移动次数不一样，会导致判断失败，举个例子说明：
A: 1->2->3->8->9
B: 5->6->8->9
其中8是交点：
- pA走：1->2->3->8->9->5->6->8
- pB走：5->6->8->9->1->2->3->8
- 时间复杂度：O(headA.length+headB.length)
- 空间复杂度：O(1)
