判断两个单链表是否有相同节点

/************************************************************************/
/* 两个不含环的单链表的相交
相交指的是结点的地址相同，而不是结点的值相同                        */
/************************************************************************/
#include<iostream>
#include<malloc.h>
#include<stdlib.h>
#define  ERROR 0
using namespace std;

struct LinkList//链表结构体
{
	int m_nValue;
	LinkList *next;
};

void InsertList(LinkList *&list)//建立一个链表
{
	LinkList *head;
	LinkList *newNode;
	int data;

	head=list;
	while(head->next)
		head=head->next;

	while(1)//链尾法构造链表
	{  
		cin>>data;
		if(data==0)
			break;
		newNode=(LinkList *)malloc(sizeof(LinkList));
		if(!newNode)
			exit(ERROR);
		newNode->m_nValue=data;
		newNode->next=NULL;
		head->next=newNode;
		head=newNode;
		head->next=NULL;
	}
}
void Traverse(LinkList *list)//输出链表
{
	LinkList *p;
	p=list->next;
	while(p)
	{
		cout<<" "<<p->m_nValue<<"    address= "<<p<<endl;
		p=p->next;
	}
}
//两个单列无环列表，从头走到尾如果有相交，最后一个节点一定相同。
int main()
{
	LinkList *first,*second;
	LinkList *fhead,*shead,*h1,*h2,*p,*q;
	int flen=0,slen=0,len;
	first=(LinkList *)malloc(sizeof(LinkList));
	first->next=NULL;
	second=(LinkList *)malloc(sizeof(LinkList));
	second->next=NULL;
	cout<<"请输入链表一的值，以0结束"<<endl;
	InsertList(first);//构造第一个链表
	cout<<endl;
	cout<<"请输入链表二的值，以0结束"<<endl;
	InsertList(second);//构造第二个链表

	///////////////////////////////////////////////// 
	//将第一个链表中从第四个结点起链接到第二个链表，构造两个相交的链表
	p=second;
	while(p->next)
		p=p->next;//找到第二个链表的尾结点
	q=first;
	for(int i=0;i<4;i++)
		q=q->next;//找到第一个链表的第四个结点
	p->next=q;//插入到第二个链表中
	//////////////////////////////////////////////////
	Traverse(first);
	cout<<endl;
	Traverse(second);
	cout<<endl;

	h1=first->next;
	fhead=first;
	while(fhead->next)//遍历链表到表尾 （执行length1次，记n2次）
	{
		fhead=fhead->next;
		flen++;
	}

	h2=second->next;
	shead=second;
	while(shead->next)//遍历链表到表尾， （执行length2次，记n1次）
	{
		shead=shead->next;
		slen++;
	}
	if(fhead==shead)//最后一个结点的地址相同，则相交
	{ 
		cout<<"两链表相交"<<endl;
		if(flen>=slen)//求两个链表长度的差值
		{
			len=flen-slen;
			while(len--) //遍历差值个步长 （执行abs(length1-length2)次）
				h1=h1->next;
		}
		else
		{
			len=slen-flen;
			while(len--)
				h2=h2->next; 
		}

		while(1)
		{

			if(h1==h2)//两个链表中地址相同的结点   （最多执行的次数为：min(length1,length2))
			{
				cout<<"第一个相交的结点："<<h1->m_nValue;
				break;
			}
			else if(h1->next&&h2->next)
			{
				h1=h1->next;
				h2=h2->next;
			} 
		}
	}
	else 
		cout<<"两链表不相交"<<endl;
	system("pause");
}