学步园

/*
第 7  题
微软亚院之编程判断俩个链表是否相交
给出俩个单向链表的头指针，比如 h1，h2，判断这俩个链表是否相交。
为了简化问题，我们假设俩个链表均不带环。
问题扩展：
1.如果链表可能有环列?
2.如果需要求出俩个链表相交的第一个节点列?


给定两单链表A、B，只给出两头指针。请问：
1、如何判断两单链表（无环）是否相交？
	判断两链表最后一个节点是否相同，如果相交，则尾节点肯定是同一节点

2、如何判断两单链表（不知是否有环）相交？

先判断是否有环，判断是否有环可以使用追逐办法，设置两个指针，一个走一步，一个走两步，
如果能相遇则说明存在环

（1）两个都没环：回到问题1
（2）一个有环，一个没环：不用判断了，肯定两链表不相交
（3）两个都有环：判断链表A的碰撞点是否出现在链表B的环中，
如果在，则相交。（相交时，环必定是两链表共有的）


3、如何寻找两相交链表（不知是否有环）的第一个相交节点？

同样，使用追逐办法先判断是否存在环，分情况讨论
（1）无环：人为构环，将链表A的尾节点指向链表B，则构成一个带环的单链表。
这个问题就转换成寻找带环单链表的环入口节点。

（2）有环：计算出两链表的长度lA、lB，（环的长度和环到入口点长度之和就是链表长度）
如果lA>lB，则链表A指针先走lA-lB，然后链表B指针开始走，两者相遇的点就是相交点
如果lB>lA，则链表B指针先走lB-lA，然后链表A指针开始走，两者相遇的点就是相交点
*/

#include<iostream>
#include<stdio.h>
using namespace std;

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

//是否是环 
node *testCy(node *h1)
{
	node *p1=h1,*p2=h1;
	while(p2!=NULL && p2->next!=NULL)
	{
		p1=p1->next;
		p2=p2->next->next;
	
	if(p1==p2)
		return p1;
	}
	return NULL;
}

//无环 判断两链表最后一个节点是否相同
bool isJoined(node *h1,node *h2)
{
	while(h1->next!=NULL){
		h1=h1->next;
	}
	while(h2->next!=NULL){
		h2=h2->next;
	}	
	return h1==h2;
}

//有环
bool isJoinedCycle(node *h1,node *h2)
{
	node *cy1=testCy(h1);
	node *cy2=testCy(h2);

	//都无环 
	if(cy1==NULL&&cy2==NULL) return isJoined(h1,h2);
	
	if(cy1==0&&cy2!=0 || cy1!=0&&cy2==0) 
		return false;

	node *p=cy1;
	while(1)
	{
		if(p==cy2||p->next==cy2) return 1;//p每次走2步
		
		p=p->next->next;
		cy1=cy1->next;
		if(p==cy1) return 0;//环结束 
	}	
}
 
void insertNode(node* &head,int data)
{
	node *x=new node;
	x->data=data;
	x->next=head;
	head=x;
}

int a[10] = {15, 14, 13, 12, 11, 10, 9, 8};  
int b[10] = {7, 6};  
int c[10] = {5, 4, 3, 2, 1};  
int main()
{
	int i;
	node *headA=NULL,*headB=NULL,*headC=NULL;
	
	for(i=0;i<8;i++)
		insertNode(headA,a[i]);
		
	for(i=0;i<2;i++)
		insertNode(headB,b[i]);	
		
	for(i=0;i<5;i++)
		insertNode(headC,c[i]);
	
	
	//case1 
	if(isJoined(headA,headB))
		printf("YES\n");
	else 
		printf("NO\n");
		
		
	node *kk=headA;//kk 8->9->10->11->12->13->14->15
	while(kk->next) 
	{
	//	printf("%d ",kk->data);
		kk=kk->next;	
	}
	
	//kk 8->9->10->11->12->13->14->15->10->...环 
	//kk是NULL 不能被赋值  若KK=NULL kk=headA->next->next;错 
	kk->next=headA->next->next;
	//headA同KK都是环 
	
	if(isJoinedCycle(headB,kk))
		printf("YES\n");
	else 
		printf("NO\n");
	
	//K2 环 
	node *k2=headC;
	while(k2->next) 
		k2=k2->next;
	k2->next=headC->next;//1 2 3 4 5 2 3...
	
	if(isJoinedCycle(headA,k2))
		printf("YES\n");
	else 
		printf("NO\n");

	return 0;
}