题目描述
输入两个链表,找出它们的第一个公共结点。
#include <iostream>
#include <vector>
#include <set>
using namespace std;
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x):val(x), next(NULL){}
};
ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2){
if(pHead1==NULL||pHead2==NULL) return NULL;
vector<ListNode*> lnvec;
ListNode *p=pHead1;
while(p!=NULL){
lnvec.push_back(p);
p=p->next;
}
set<ListNode*> lnset;
p=pHead2;
while(p!=NULL){
lnset.insert(p);
p=p->next;
}
int len=lnvec.size();
for(int i=0;i<len;i++){
if(lnset.count(lnvec[i]))
return lnvec[i];
}
return NULL;
}
int main(){
set<int> s;
s.insert(3);
s.insert(2);
s.insert(6);
cout<<s.count(5)<<endl;
system("pause");
}
判断两个单链表是否交叉思路:
分别遍历两个单链表,记录最后一个结点,看是否为同一个结点,如果是,则交叉。