求两个链表是否相交总结


		    求两个链表是否相交总结 
求两个单链表是否相交分三种情况讨论:
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;
}

补充：综合编程 , 其他综合 ,