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

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

思路：

①首先分别求出两个链表的长度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;

}