剑指offer 两个链表的第一个公共结点

刺骨的言语ヽ痛彻心扉 2021-11-05 20:32 225阅读 0赞

# [剑指offer题型分类及各题的代码及解题思路][offer] #

## 题目描述 ##

输入两个链表，找出它们的第一个公共结点。

结点定义如下：

struct ListNode \{  
    int val;  
    struct ListNode \*next;  
    ListNode(int x) :  
            val(x), next(NULL) \{  
    \}  
\};

分析：

公共结点的意思是两个链表相遇之后后面的数据和next都是一样的。

解法一：

思路：`找出2个链表的长度，然后让长的先走两个链表的长度差，然后再一起走（因为2个链表用公共的尾部）`

C++实现代码如下：

ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) 
    {
    	int len1 = FindListLength(pHead1);
    	int len2 = FindListLength(pHead2);
    	//使两个链表长度相同，这样同步往后走，就会找到第一个公共结点了
    	if(len1 > len2)
    	{
    		pHead1 = WalkStep(pHead1, len1 - len2);
    	}
    	else
    	{
    		pHead2 = WalkStep(pHead2, len2 - len1);
    	}
    	
    	//两个链表现在长度相同，同步往后走
    	while(pHead1 != NULL)
    	{
    		if(pHead1 == pHead2)
    			return pHead1;
    		
    		pHead1 = pHead1->next;
    		pHead2 = pHead2->next;
    	}
    	return NULL;
    }
    
    int FindListLength(ListNode* p)    //求链表长度
    {
    	if(NULL == p)
    		return 0;
    	
    	int sum = 1;
    	while(p = p->next)
    	{
    		sum++;
    	}
    	return sum;
    }
    
    ListNode* WalkStep(ListNode* p, int n)    //让长的链表先走多的步数
    {
    	while(n--)
    	{
    		p = p->next;
    	}
    	return p;
    }

解法二：（[思路清晰，代码简洁明了][Link 1]）

`思路：假定 List1长度: a+n  List2 长度:b+n, 且 a<b。`

开始，p1走(a+n)步，p2和p1同步，也走了(a+n)步，此时，p1走到了链表1的尾部，而p2所在的链表2还有(b-a)未走，让p1指向链表2的头，然后在一起走(b-a)步，p2走到了链表2的尾部，再让p2指向链表的头，这时候，两个指针遍历链表的剩余长度一样长，这时候一起走，如果有公共的一部分结点，必定会相遇，相遇点为第一个公共的结点。

总结：相当于p1和p2都去遍历两个链表，前者遍历(a+n+b)步，后者遍历(b+n+a)步，之后两者相遇点就为公共部分的首结点。

（光看很难理解，自己画个图就理解了）

C++实现代码如下：

ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) 
    {
    	ListNode* p1 = pHead1;
    	ListNode* p2 = pHead2;
    
    	while(p1 != p2) 
    	{
    		if(p1 != NULL) p1 = p1->next;   
    		if(p2 != NULL) p2 = p2->next;
    		if(p1 != p2) 
    		{                  
    			if(p1 == NULL) p1 = pHead2;
    			if(p2 == NULL) p2 = pHead1;
    		}
    	}
    	return p1;
    }

[offer]: https://blog.csdn.net/qq_26079093/article/details/96605538
[Link 1]: https://www.nowcoder.com/questionTerminal/6ab1d9a29e88450685099d45c9e31e46?f=discussion