题解 | #两个链表的第一个公共结点#

解题思路

分别遍历两个链表，分别求出结点个数：

若长度不等，求二者差值diff，长链表 的循环指针从头开始 先向后移动 diff 次，短链表 循环指针指向首结点，使两指针所在位置到链表尾部距离相同。

若长度相同，不做操作。

两循环指针同时向后移动，如果指向了相同结点，返回该结点元素；否则当到达尾部NULL时，表明两链表无公共部分。

代码实现

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        if(!pHead1 || !pHead2)
        	return NULL;
		ListNode* p1 = pHead1;
		ListNode* p2 = pHead2;
		int count1,count2,diff;
		count1 = count2 =0;
	  
	  //计算链表1的结点总数。
		while(p1){
			count1++;
			p1=p1->next;
		}
	  
	  //计算链表2的结点总数。
		while(p2){
			count2++;
			p2=p2->next;
		}
		p1 = pHead1;
		p2 = pHead2;
	  //较长链表的循环指针首先向后移动 diff 个结点。
		if(count1>count2){
			diff = count1-count2;
			while(diff>0){
				p1 = p1->next;  
				diff--; 
			}  
		}else{
			diff = count2-count1;
			while(diff>0){
				p2 = p2->next;
				diff--;
			}
		}
	  //两个循环指针同时向后移动，指向同一结点时找到了第一个公共结点，返回。
		while(p1){
			if(p1==p2)
				return p1;
			p1 = p1->next;
			p2 = p2->next;
			
		}
		return NULL;  //两循环指针都到达尾部，说明无公共结点
	}
};

时间复杂度

时间复杂度：若两链表结点总数为n，最坏情况下遍历2n个结点，故时间复杂度为O(n)。

空间复杂度：定义变量个数和输入规模无关，为O(1)。