判断两个单链表是否相交，若相交，求节点（链表不带环）

﹏ヽ暗。殇╰゛Y 2022-05-11 00:56 163阅读 0赞

先理解一下题目的意思，单链表的相交和普通两条线的相交一样吗？  
![在这里插入图片描述][70]  
所以当我们把其换成节点就可以变成下面这样：

![在这里插入图片描述][70 1]  
先判断链表是否相交，我们可以运用两个链表相交后就变成了一条链表这个特性来判断，因为如果两条链表相交，那么这两条链表的最后一个节点一定是同一个节点，否则不可能相交

//1表示有交点，0表示没有交点
    	int IsIntersection(Node *first1, Node *first2)
    	{
    		assert(first1);
    		assert(first2);
    		while (first1->next != NULL)
    		{
    			first1 = first1->next;
    		}
    		while (first2->next != NULL)
    		{
    			first2 = first2->next;
    		}
    		if (first1 == first2)
    		{
    			return 1;
    		}
    		return 0;
    	}

接下来，我们考虑交点的问题，如何才能找到交点？  
两条链表在交点之后的长度肯定是一样的，在交点之前的长度是不一样的，我们可以计算出两条链表长度的差值k，然后让长的链表先走k步，再让两条链表同时走，当相同的时候，就表示走到交点了，这时候返回即可  
![在这里插入图片描述][70 2]

int GetLength(Node *first)
    	{
    		assert(first);
    		int count = 0;
    		while (first != NULL)
    		{
    			count++;
    			first = first->next;
    		}
    		return count;
    	}
    
    	Node *IntersectionNode(Node *first1, Node *first2)
    	{
    		assert(first1);
    		assert(first2);
    		int count1 = GetLength(first1);
    		int count2 = GetLength(first2);
    		Node *longer = first1;
    		Node *shorter = first2;
    		int k = count1 - count2;
    		if (count1 < count2)
    		{
    			longer = first2;
    			shorter = first1;
    			k = count2 - count1;
    		}
    		while (k--)
    		{
    			longer = longer->next;
    		}
    		while (longer != shorter)
    		{
    			longer = longer->next;
    			shorter = shorter->next;
    		}
    		return longer;
    	}

[70]: /images/20220511/83e01162b28e44daa15483438e74398c.png
[70 1]: /images/20220511/a8cf0284a3d9412992e8a16739f07127.png
[70 2]: /images/20220511/129c04e513a64041a0bfe6a248e52226.png