思路:
①首先分别求出两个链表的长度之差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;
}
// 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;
}
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;
}
分享到:
相关推荐
判断通过空间的坐标点确定的选段是否相交,相交的求出交点
(1)定义一个Point类,其属性包括点的坐标,提供计算两点之间距离的方法; (2)定义一个圆形类,其属性包括圆心和半径;...(3)创建两个圆形对象,提示用户输入圆心坐标和半径,判断两个圆是否相交,并输出结果。
自己写的 有限长度线段 对象。 提供3个方法: 1. 判断两个线段是否相交; 2. 获取相交点; 3. 获取 对象线段第一个端点 和 相交点 之间的距离;
直线相交容易判断,但判断两条线段是否相交有些困难,本代码不但能判断是否相交,还能求出交点坐标。
由于项目需要,写了两个函数,IsLineSegmentCross和GetCrossPoint,对于各种情况都能很好适应,并正确的求出交点。通过了各种测试,完美的实现个算法真不容易啊! 这个是连带一个MFC测试的程序工程VC6.0源码!
Unity3D判断两个物体相交脚本 Posted on 2013年02月25日 by U3d / Unity3D脚本/插件/被围观 285 次 Unity3D中
给出两个单向链表的头指针(如图3-8 所示),比如h1、h2,判断这两个链表是否 相交。这里为了简化问题,我们假设两个链表均不带环。
编程实现了如何判断一个平面里的两条线段是否相交!
分析与解法 这样的一个问题,也许我们平时很少考虑。但在一个大的系统中,如果出现两个链表相 交的情况,而且释放了其中一个链表的...的两个链表,我们希望在释放一个链表之前知道是否有其他链表跟当前这个链表相交。
本范例通过扩展,实现计算地图上绘制的两个圆的相交交点的坐标值,并将其展现在地图上。
实现了一个简单的java版本的单链表,链表反转和链表是否相交如果相交求相交节点。关于链表是否相交是一次阿里的面试的在线试题,挂的很彻底。然后就在网上找了几个实现思路自己用java做了一个简单的实现....
geotools 判断几何要素的交点 当时想到用的GDAL 但是 交点函数返回的对象总是null , 改用 GeoTools 这个库,需要用到jar 到官网上下载,主要是jts-core-1.16.0.jar
1,判断两个线段是否相交,2,判断交点是否在线段上,VS2015 C#完整项目包,下载即可验证。
用VC6.0实现的MFC单文档程序,用鼠标在屏幕上任意画两条直线,判断两直线是否相交。
8.判断单链表是否有环?如何找到环的“起始”点?如何知道环的长度? 9.判断两个单链表是否相交 10.两个单链表相交,计算相交点 11.用链表模拟大整数加法运算 12.单链表排序 13.删除单链表中重复的元素
判断任意位置旋转的矩形是否相交,相交输出true,否则输出false。
perl 依四点的坐标,判断两线段是否相交,若相交求出交点。
判断单链表是否有环?如何找到环的“起始”点?如何知道环的长度? 9.判断两个单链表是否相交 10.两个单链表相交,计算相交点 11.用链表模拟大整数加法运算 12.单链表排序 13.删除单链表中重复的元素
原文地址 http://www.cnblogs.com/topcss/p/3575248.html ,基于该作者的代码基础上进行简单修改,使其在openlayers3上可用,有兴趣可以去看一下