学步园

http://blog.csdn.net/v_JULY_v/article/details/6126406

微软亚院之编程判断俩个链表是否相交
给出俩个单向链表的头指针，比如h1，h2，判断这俩个链表是否相交。
为了简化问题，我们假设俩个链表均不带环。

问题扩展：
1.如果链表可能有环列?
2.如果需要求出俩个链表相交的第一个节点列?

//这一题，自己也和不少人讨论过了，
//更详细的，请看这里：
//My sina Blog：
//http://blog.sina.com.cn/s/blog_5e3ab00c0100le4s.html

1.首先假定链表不带环
那么，我们只要判断俩个链表的尾指针是否相等。
相等，则链表相交；否则，链表不相交。
2.如果链表带环，
那判断一链表上俩指针相遇的那个节点，在不在另一条链表上。
如果在，则相交，如果不在，则不相交。

所以，事实上，这个问题就转化成了：
1.先判断带不带环
2.如果都不带环，就判断尾节点是否相等
3.如果都带环，判断一链表上俩指针相遇的那个节点，在不在另一条链表上。
如果在，则相交，如果不在，则不相交。

//用两个指针，一个指针步长为1，一个指针步长为2，判断链表是否有环
bool check(const node* head)
{
    if(head==NULL)
      return false;
    node *low=head, *fast=head->next;
    while(fast!=NULL && fast->next!=NULL)
    {
        low=low->next;
        fast=fast->next->next;
        if(low==fast) return true;
    }
    return false;
}

//如果链表可能有环，则如何判断两个链表是否相交
//思路：链表1 步长为1，链表2步长为2 ，如果有环且相交则肯定相遇，否则不相交
list1 head: p1
list2 head: p2
while( p1 != p2 && p1 != NULL && p2 != NULL )
[b]//但当链表有环但不相交时，此处是死循环。![/b]
{
      p1 = p1->next;
      if ( p2->next )
         p2 = p2->next->next;
      else
         p2 = p2->next;
}
if ( p1 == p2 && p1 && p2)
   //相交
else
  //不相交
所以，判断带环的链表，相不相交，只能这样：
如果都带环，判断一链表上俩指针相遇的那个节点，在不在另一条链表上。
如果在，则相交，如果不在，则不相交。(未写代码实现，见谅。:)..
------------------
http://blog.csdn.net/miao6664659/article/details/8135383

http://blog.csdn.net/miao6664659/article/details/8132752

typedef struct LNode
{
	int data;
	struct LNode* next;
}LNode,*LinkList;

LinkList createList(LinkList begin)
{
	begin=(LinkList)malloc(sizeof(LNode));
	begin->next=NULL;
	int len;
	scanf("%d",&len);
	begin->data=len;
	for(int i=0;i<len;i++)
	{
		LinkList p=(LinkList)malloc(sizeof(LNode));
		int data;
		scanf("%d",&data);
		p->next=begin->next;
		p->data=data;
		begin->next=p;
	}
	return begin;
}
void traverse(LinkList head)
{
	int len=head->data;
	head=head->next;
	for(int i=0;i<len+1;i++)
	{
		cout<<head->data<<" ";
		head=head->next;
	}
	cout<<endl;
}
LinkList jiaochaTest(LinkList head)
{
	int len=head->data;
	head=head->next;
	for(int i=0;i<len-1;i++)
		head=head->next;
	return head;
}
#include <windows.h>
LinkList IsCircle(LinkList head)//返回追尾点
{
	LinkList slow,fast;
	slow=fast=head->next;
	while(slow&&fast)
	{
		if(slow->next==fast->next->next)
			return slow->next;
		slow=slow->next;
		fast=fast->next->next;
	}
	return NULL;
}
//返回相交节点
LinkList findFirstNode(LinkList p,LinkList q)
{
	while(p!=q)
	{
		p=p->next;
		q=q->next;
	}
	return q;
}

BOOL Test(LinkList p,LinkList q)
{
	LinkList head1=p->next;
	LinkList head2=q->next;
	while(head1!=head2&&head1!=NULL&head2!=NULL)
	{
		head1=head1->next;
		if(head2->next)
			head2=head2->next->next;
		else
			head2=head2->next;
	}
	if(head1==head2&&head1&&head2)
		return TRUE;
	else
		return FALSE;
}


void main()
{
	LinkList head=NULL;
	head=createList(head);
	LinkList p=jiaochaTest(head);
	p->next=head->next->next->next;
	traverse(head);
	//LinkList b=IsCircle(head);//b为追尾点
	LinkList head2=NULL;
	head2=createList(head2);
	LinkList temp=NULL;
	int len=head2->data;
	temp=head2->next;
	for(int i=0;i<len-1;i++)
		temp=temp->next;
	temp->next=head->next->next->next->next;
	traverse(head2);
	BOOL test=Test(head,head2);
	if(test)
		cout<<"交叉"<<endl;
	LinkList b=IsCircle(head);
	if(b)//打印出追尾点
		cout<<b->data<<endl;
	b=findFirstNode(b,head->next);
	cout<<b->data<<endl;
}