单链表判断有无公共节点是个比较有趣的问题。这里所说的公共节点指的是完全相同的节点，不同与一般意义上的节点元素相同。相交单链表简单的都会是如下形式（有环除外）：

     粗略分析，容易想到就是暴力法，双重循环寻找公共节点。

     关于单链表的判断有无公共节点，除了暴力法之外，还有很多方法可以尝试。下面简单列举几种。

     可以尝试hash，如果两个节点的首地址相同，则该节点必定相同，可以以空间换取时间，先处理其中一个单链表，建立hash表，然后处理另外一个判断有无公共节点，时间复杂度为O(max(n,m))，空间复杂度为O(min(n,m))。

     由于单链表的特殊性，若只需判断有无公共节点，可以直接比较最后一个节点，相同则有公共节点，不通则没有公共节点。

当然，可以尾部对齐，然后将较长单链表的指针移到与较短的单链表头指针一致的地方，之后判断两个指针是否相同，不同则同时后移；相同则证明有公共节点并且找到公共节点开始位置。此算法时间复杂度为O(max(n,m))，空间复杂度为O(1)。

     还有另外一种较为好的方法，即将其中一个单链表接到另外一个的尾部，然后判断有无环。若两个单链表相交，则必然有环，环的入口就是交点；若无环，则必无公共节点。下面问题就转化为求单链表有无环且在有环情况下找到环的入口。这样做的前提是单链表无环。如图：

     判断环可以类比追击问题，设置两个步长，然后看二者能否在出发后相遇，能则有环；否则无环。当然步长可以有多种组合，考虑到是离散量即相遇时不能取小数，所以去步长为1、2比较合适，这点在后面求环的入口是非常重要的。时间复杂度为O(n)，空间复杂度为O(1)。

     下面是求环的入口示意图：

       两个单链表总得有如下3中可能组合（具体说明明见图）：

下面贴段代码：

#include<iostream>using namespace std;struct SNode{	SNode *next;	int key;};/**********************************参数：链表头结点引用*功能：初始化单链表头结点*返回值：空**********************************/void Inite(SNode *&tempHead){	tempHead=new SNode;	tempHead->next=NULL;}/**********************************参数：链表头结点*功能：尾插法插入单个元素*返回值：无**********************************/void Insert(SNode *tempHead,int tempKey){	if(NULL==tempHead)return ;	SNode *pre=tempHead,*cur=tempHead->next;	while(cur!=NULL)	{		pre=cur;		cur=cur->next;	}	SNode *p;	p=new SNode;	p->key=tempKey;	p->next=NULL;	pre->next=p;}/**********************************参数：链表头结点*功能：判断单链表是否有环*返回值：有环，true；否则，false**********************************/bool IsLoop(SNode *tempHead){	if(NULL==tempHead||NULL==tempHead->next)		return false;	SNode *slow=tempHead->next,*fast=slow;	while(fast!=NULL&&fast->next!=NULL)	{		slow=slow->next;		fast=fast->next->next;		if(slow==fast)return true;	}	return false;}/**********************************参数：链表头结点*功能：计算单链表环的入口位置*返回值：存在则返回环的入口位置，否则返回NULL**********************************/SNode* GetEntryLoopNode(SNode *tempHead){	if(NULL==tempHead||NULL==tempHead->next)		return NULL;	SNode *slow=tempHead->next,*fast=slow;	while(fast!=NULL&&fast->next!=NULL)	{		slow=slow->next;		fast=fast->next->next;		if(slow==fast)break;	}	if(NULL==fast&&NULL==fast->next)		return NULL;	slow=tempHead->next;	while(slow!=fast)	{		slow=slow->next;		fast=fast->next;	}	return fast;}/**********************************参数：链表头结点*功能：计算链表长度*返回值：链表长度**********************************/int GetLength(SNode *tempHead){	int len=0;	if(NULL==tempHead)		return -1;	SNode *p=tempHead->next;	while(p!=NULL)	{		++len;		p=p->next;	}	return len;}/**********************************参数：两链表头结点*功能：计算两个单链表公共节点开始位置*返回值：存在则返回开始位置，否则返回NULL**********************************/SNode* FirstComNode(SNode *tempHead1,SNode*tempHead2){	int len1=GetLength(tempHead1);	int len2=GetLength(tempHead2);	if(-1==len1||-1==len2)		return NULL;	SNode *p,*q;//p指向较长者，q指向较短者	cout<<"len1="<<len1<<"  len2="<<len2<<endl;	//保证都从倒数第n个比较，n为len1,len2较小者	if(len1>len2)	{		p=tempHead1->next;		q=tempHead2->next;		int tempLen=len1;		while(tempLen>len2)		{			cout<<p->key<<"@    ";			--tempLen;			p=p->next;		}	}	else	{		p=tempHead2->next;		q=tempHead1->next;		int tempLen=len2;		while(tempLen>len1)		{			cout<<p->key<<"&    ";			--tempLen;			p=p->next;		}	}	cout<<endl;	while(p!=NULL&&q!=NULL&&p!=q)	{		p=p->next;		q=q->next;	}	if(p==q)		return p;	return NULL;}/**********************************参数：两个链表头结点*功能：判断单链表是否相交*返回值：相交，true；否则，false*注意：此时单链表结构改变了**********************************/bool IsHasComNode(SNode *tempHead1,SNode*tempHead2){	if(NULL==tempHead1||NULL==tempHead1)		return false;	if(tempHead1->next!=NULL)	{		if(tempHead2->next!=NULL)		{			SNode *temp=tempHead1->next;			tempHead1->next=tempHead2->next;			SNode *cur=tempHead2;			while(cur->next!=NULL)				cur=cur->next;			cur->next=temp;		}	}	else tempHead1=tempHead2;	return IsLoop(tempHead1);}int main(){	SNode *head1,*head2;	Inite(head1);	Inite(head2);	for(int i=0;i<10;i++)		Insert(head1,i);	Insert(head2,20);	head2->next->next=head1->next->next->next;//	if(IsLoop(head1))		cout<<"有环"<<endl;	else cout<<"无环"<<endl;	SNode * firComNode=FirstComNode(head1,head2);	if(firComNode!=NULL)		cout<<"最开始公共节点为："<<firComNode->key<<endl;	else cout<<"无公共节点"<<endl;	 	if(IsHasComNode(head1,head2))		cout<<"有公共节点"<<endl;	else cout<<"无公共节点"<<endl;	system("pause");	return 0;}

     由于时间不足，缺乏辩证，如有错误，欢迎斧正！