思路一：哈希表法
把其中一个链表中的值存入哈希表中，然后在这个构建的哈希表中寻找另一链表中的值
/**
* 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)