📟作者主页：慢热的陕西人

🌴专栏链接：力扣刷题日记

📣欢迎各位大佬👍点赞🔥关注🚓收藏，🍉留言

牛客热题：两个链表的第一个公共节点

题目链接：

两个链表的第一个公共结点_牛客题霸_牛客网 (nowcoder.com)

方法一：哈希

思路

• 对第一个链表的所有节点都插入到哈希表
• 紧接着遍历第二个链表，当判断遍历的节点哈希表中存在过
• 那么我们就认为这是公共链表的第一个节点。否则，则认为没有公共节点

代码

    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) 
	{
		if(pHead1 == nullptr || pHead2 == nullptr) return nullptr;
		unordered_set<ListNode*> hash;
		ListNode* p1 = pHead1;
		while(p1 != nullptr)
		{
			hash.insert(p1);
			p1 = p1->next;
		}
		ListNode* p2 = pHead2;
		while(p2 != nullptr)
		{
			if(hash.count(p2)) return p2;
			p2 = p2->next;
		}

		return nullptr;
    }

复杂度

时间复杂度：O(N) ,遍历了两个链表

空间复杂度：O(N) ,创建了一个哈希表用于存储第一个链表的节点

方法二：

思路

使用两个指针N1,N2，一个从链表1的头节点开始遍历，我们记为N1，一个从链表2的头节点开始遍历，我们记为N2。

让N1和N2一起遍历，当N1先走完链表1的尽头（为null）的时候，则从链表2的头节点继续遍历，同样，如果N2先走完了链表2的尽头，则从链表1的头节点继续遍历，也就是说，N1和N2都会遍历链表1和链表2。

因为两个指针，同样的速度，走完同样长度（链表1+链表2），不管两条链表有无相同节点，都能够到达同时到达终点。

（N1最后肯定能到达链表2的终点，N2肯定能到达链表1的终点）。

所以，如何得到公共节点：

• 有公共节点的时候，N1和N2必会相遇，因为长度一样嘛，速度也一定，必会走到相同的地方的，所以当两者相等的时候，则会第一个公共的节点
• 无公共节点的时候，此时N1和N2则都会走到终点，那么他们此时都是null，所以也算是相等了。

代码

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

		return p1;
    }

复杂度

时间复杂度：O(M + N), 其中M和N为链表的长度

空间复杂度：O(1), 使用了常数个变量