剑指offer-两个链表的第一个公共结点

2016/05/24 C和C++基础

题目描述

输入两个链表,找出它们的第一个公共结点。

#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");
}

判断两个单链表是否交叉思路:

分别遍历两个单链表,记录最后一个结点,看是否为同一个结点,如果是,则交叉。

Search

    Post Directory