链表相交问题

叁歲伎倆 2022-05-08 08:18 234阅读 0赞

本来想自己写，写了一半发现一篇文章，解释写得简单易懂，我就直接拿过来了。

这个问题值得反复地写，锻炼链表coding能力的好题。

![Center][]

![Center 1][]

![Center 2][]

//如果两个链表都不带环
    int NotCycleCheckCross(pLinkNode head1,pLinkNode head2)
    {
        pLinkNode list1 = head1->next;
    	pLinkNode list2 = head2->next;
    	if ((NULL==list1 )||(NULL==list2))
    	{
    		return 0;      //不相交
    	}
    	while (NULL != list1->next)
    	{
    		list1 = list1->next;
    	}
    	while (NULL != list2->next)
    	{
    		list2 = list2->next;
    	}
    	if (list1==list2)
    	{
    		return 1;      //相交
    	}
    	return 0;          //不相交
    }
    
     
    
    //链表带环，判断两个链表是否相交
    int CycleCheckCross(pLinkNode meet1, pLinkNode meet2)
    {
    	pLinkNode cur = meet1->next;
    	if (meet1 == meet2)
    	{
    		return 1;     //链表相交
    	}
    	while ((cur != meet1)&&(cur!=meet2))
    	{
    		cur = cur->next;
    	}
    	if (cur == meet2)
    	{
    		return 1;   //链表相交
    	}
    	return 0;       //不相交
    }
    //将上面两个函数封装成一个函数
    
    int CheckCross(pLinkNode head1, pLinkNode head2)          //参数为两个头结点
    
    {
    	pLinkNode fast = NULL;
    	pLinkNode slow = NULL;
    	pLinkNode meet1 = NULL;
    	pLinkNode meet2 = NULL;
    	if (head1->next == NULL || head2->next == NULL)
    	{
    		return 0;          //至少一个链表为空链表，则两个链表一定不相交
    	}
    	fast = head1->next;
    	slow = head1->next;
    	while (fast&&fast->next)           //判断链表head1是否带环
    	{
    		fast = fast->next->next;
    		slow = slow->next;
    		if (fast == slow)
    		{
    			meet1 = fast;
    			break;
    		}
    	}
    	fast = head2->next;
    	slow = head2->next;
    	while (fast&&fast->next)           //判断链表head2是否带环
    	{
    		fast = fast->next->next;
    		slow = slow->next;
    		if (fast == slow)
    		{
    			meet2 = fast;
    			break;
    		}
    	}
    	if ((meet1 == NULL) && (meet2 == NULL))       //如果两个链表都不带环
    	{
    		return NotCycleCheckCross(head1, head2);
    	}
    	else if (meet1&&meet2)                        //如果两个链表都带环
    	{
    		return CycleCheckCross(meet1, meet2);
    	}
    	//如果两个链表一个带环一个不带环，则一定不相交直接返回0
    	return 0;            //不相交
    
    }

原文[https://blog.csdn.net/lf\_2016/article/details/51756644][https_blog.csdn.net_lf_2016_article_details_51756644]

[Center]: /images/20220508/10667a93f4844171bc45620df267301c.png
[Center 1]: /images/20220508/1126d620a6234085a24efa592219a0d2.png
[Center 2]: /images/20220508/1639d1b3fba748468524f173758a4595.png
[https_blog.csdn.net_lf_2016_article_details_51756644]: https://blog.csdn.net/lf_2016/article/details/51756644