判断两个单链表是否相交，并找到交点

思路：

①首先分别求出两个链表的长度a

②让长度长的链表先走a下

③然后两个链表一起走，如果相等，并且都不为空，那么就说明两个链表是相交的。

代码实现如下：

// IsLinkMeet1.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
using namespace std;

typedef struct node
{
int data;
struct node* next;

}Node;

Node* create_Node_NoRing(int a[],int len)
{
Node* head,*p,*q;
p=new Node();
p->data=a[0];
head=p;
p=new Node();
p->data=a[1];
head->next=p;

for (int i=2;i<len;i++)
{
q=new Node();
q->data=a[i];
p->next=q;
p=q;
}
p=NULL;
return head;
}

bool IsMeeting(Node* head1,Node* head2,int lena,int lenb)
{
Node* fast,*slow;
int duff=0;
if (lena>lenb)
{
duff=lena-lenb;
fast=head1;
slow=head2;
}
else
{
duff=lenb-lena;
fast=head2;
slow=head1;
}
while(duff)
{
fast=fast->next;
duff--;
}
while(fast!=slow && fast!=NULL && slow!=NULL)
{
slow=slow->next;
fast=fast->next;
}
if (fast==slow && fast!=NULL && slow!=NULL )
{
return true;
}
return false;

}
int _tmain(int argc, _TCHAR* argv[])
{
int a[]={1,2,3,4,5,6,7};
//int b[]={12,11,10,9,5,6,7};
int b[]={12,11,10};
int lena=sizeof(a)/sizeof(int);
int lenb = sizeof(b)/sizeof(int);
Node* head1 = create_Node_NoRing(a,lena);
Node* head2 = create_Node_NoRing(b,lenb);
cout<<IsMeeting(head1,head2,lena,lenb)<<endl;

system("pause");
return 0;
}

下面的程序是找到两个链表的交点

Node* FirstMeet(Node* head1,Node* head2,int lena,int lenb)
{
Node* fast,*slow;
int duff=0;
if (lena>lenb)
{
duff=lena-lenb;
fast=head1;
slow=head2;
}
else
{
duff=lenb-lena;
fast=head2;
slow=head1;
}
while(duff)
{
fast=fast->next;
duff--;
}
while(fast->data!=slow->data && fast!=NULL && slow!=NULL)
{
slow=slow->next;
fast=fast->next;
}
if (fast->data==slow->data && fast!=NULL && slow!=NULL )
{
return fast;
}
return NULL;

}