求两个链表是否相交总结
求两个单链表是否相交分三种情况讨论:
1,如果两个链表一个有环，一个无环则一定不相交
2.如果都没有环，则判断两个链表的最后节点是否相同，如果相同则相交，不相同则不相交。
3.如果都有环，则判断一个链表环里的节点是否是另一个链表环里的节点。如果是则相交，如果不是则不相交。
现在的问题是如何判断一个链表是否有环?
我们可以设两个指针p1,p2。p1一次移动一步，p2一次移动两步，p2先移动，a.如果最后p2赶上了p1即p2==p1则有环,且此时的p1（或者p2）在环内。
b.如果p2或者p1移动若干步之后为NULL则说明没有环。
具体代码如下:
// 判断链表是否有环.cpp : 定义控制台应用程序的入口点。
#include "stdafx.h"
#include <iostream>
using namespace std;
struct ListNode
{
char data;
ListNode * next;
};
//判断是否有环
//phead链表头结点,若果有环catchNode为p1与p2相遇时的节点,如果无环lastNode保存链表最后的节点
bool isCircle(ListNode * phead,ListNode * & catchNode,ListNode * & lastNode)
{
if(phead==NULL)
{
lastNode=NULL;
return false;
}
ListNode *p1=phead;
ListNode *p2=phead->next;
if(p2==NULL)
{
lastNode=phead;
return false;
}
while(p2 && p1 && p1!=p2)
{
if(p2->next!=NULL)
p2=p2->next;
if(p2->next==NULL)
{
lastNode=p2;
return false;
}
p2=p2->next;
p1=p1->next;
}
catchNode=p1;
return true;
}
//判断两个链表是否相交
bool isIntersect(ListNode * phead1,ListNode * phead2)
{
ListNode * catchNode1=NULL;
ListNode * catchNode2=NULL;
ListNode * lastNode1=NULL;
ListNode * lastNode2=NULL;
bool iscircle1=isCircle(phead1,catchNode1,lastNode1);
bool iscircle2=isCircle(phead2,catchNode2,lastNode2);
//一个有环一个无环则一定不相交
if(iscircle1!=iscircle2)
return false;
//若果两个都没有环
if(!iscircle1 && !iscircle2)
{
return lastNode1==lastNode2;
}
//若果两个都有环
else
{
//判断一个链表环里的节点是否是另一个链表环里的节点
if(catchNode1==catchNode2)
return true;
else
{
ListNode * temp=catchNode1->next;
while(temp!=catchNode1)
{
if(temp==catchNode2)
return true;
temp=temp->next;
}
return false;
}
}
}
//////////下面是测试用定义的函数/////
ListNode * CreateListNode(char data)
{
ListNode * pNode=new ListNode();
pNode->data=data;
pNode->next=NULL;
return pNode;
}
void SetNext(ListNode * parent,ListNode * child)
{
parent->next=child;
}
int _tmain(int argc, _TCHAR* argv[])
{
//创建两个无环相交的链表
ListNode * pA=CreateListNode('A');
ListNode * pB=CreateListNode('B');
ListNode * pC=CreateListNode('C');
ListNode * pG=CreateListNode('G');
ListNode * pH=CreateListNode('H');
ListNode * pI=CreateListNode('I');
SetNext(pA,pB);
SetNext(pB,pC);
SetNext(pC,pG);
SetNext(pG,pH);
SetNext(pH,pI);
SetNext(pI,pC);
ListNode * phead1=pA;
ListNode * pD=CreateListNode('D');
ListNode * pE=CreateListNode('E');
ListNode * pF=CreateListNode('F');
SetNext(pD,pE);
SetNext(pE,pF);
SetNext(pF,pB);
ListNode * phead2=pD;
bool isintersect=isIntersect(phead1,phead2);
cout<<isintersect<<endl;
system("PAUSE");
return 0;
}