53-判断两个单链表是否相交，返回相交的第一个结点（带头结点的单链表）

深藏阁楼爱情的钟 2022-12-24 13:58 141阅读 0赞

方法1：  
先计算两个链表的长度，然后让指针p先在长的链表上走 差值 个， 然后指针p和指向短的链表的指针q同步向后走，并判断p和q是否相等，如果相等，则返回p。  
缺点是调用两次求长度的函数。时间复杂度较高。

HeadList *IsIntersect(HeadList *l1, HeadList *l2)
    {
        
    	if(l1==NULL||l2==NULL) return NULL;
    	int len1=GetLength(l1);
    	int len2=GetLength(l2);
    	HeadList *p=len1-len2>0?l1:l2;//p指向的是长的链表
    	HeadList *q=len1-len2>0?l2:l1;//p指向的是短的链表
    	int diff=fabs(len1-len2);//求差值的绝对值
    	while(diff)
    	{
        
    		p=p->next;
    		diff--;
    	 } 
    	while(p!=NULL)
    	{
        
    		if(p==q) return p;
    		p=p->next;
    		q=q->next;
    	}
    	return NULL;
     }

方法2：  
两个指针p和q分别指向两个链表，同步向后遍历，当一个指针为NULL，让他指向另一个链表，直到p和q相等。p和q相等的两种情况： 1、指向了第一个相交的节点 2、 p和q都为NULL。  
这个方法不错，代码量少且效率高。

HeadList *IsIntersect2(HeadList *l1, HeadList *l2)
    {
        
         if(l1==NULL||l2==NULL) return NULL;
         HeadList *p=l1;
         HeadList *q=l2;
         while(p!=q)
         {
        
         	p=p==NULL?l2:p->next;
         	q=q==NULL?l1:q->next;
    	 }
    	 return p;
    }