方法一:哈希表
思路:
- 先创建一个
unordered_set,存放ListNode*类型的变量 - 先遍历其中一个链表,把所有节点的指针放在set中
- 再遍历另一个链表,查找是否存在一个节点已经在set中,如果存在则说明这是它们的相交节点的指针,返回这个指针,如果不存在则说明不存在相交节点,返回NULL
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
unordered_set<ListNode*>hash;
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *A=headA,*B=headB;
while(A!=NULL){
hash.insert(A);
A=A->next;
}
while(B!=NULL){
if(hash.find(B)!=hash.end())
return B;
else
B=B->next;
}
return NULL;
}
};
方法二:双指针
思路:
- 让指针A和指针B分别指向headA和headB;A和B同时开始往后走,每次走一步,当A走到空时,就让A指向headB继续往后走;当B走到空时就让B指向headA继续往后走
- 最终一定会出现A=B,这时有两种情况:①A和B都指向空,这说明两个链表没有相交节点;②A和B指向同一个非空节点,这个节点就是相交节点
最终会出现A=B的原因:假设两个链表长度分别为a和b,A是先走完a,再走完b,走的长度是a+b;B是先走完b,再走完a,走的长度是b+a,二者走的路程一样,最终肯定会指向同一个节点。
/**
* 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) {
ListNode*A=headA,*B=headB;
while(true){
if(A==NULL && A!=B)
A=headB;
if(B==NULL && B!=A)
B=headA;
if(A==B)
return A;
if(A==NULL && B==NULL)
return NULL;
A=A->next;
B=B->next;
}
return NULL;
}
};