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

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:

	// 对于输入  {1,2,3,4,5},{},{6,7,8}
	// 这个意思 指pHead2 从6开始
	// 所以 我的写法是不行的
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {

		// if(pHead1 == nullptr && pHead2!=nullptr)
		// {
		// 	if(pHead1->next !=nullptr) return pHead1->next;
			
		// 	// return pHead2;
		// }

		// if(pHead2 == nullptr && pHead1!=nullptr)
		// {
		// 	if(pHead2->next !=nullptr) return pHead2->next;
		// }
		if(pHead1==nullptr || pHead2==nullptr)
		{
			return nullptr;
		}
		// 先判断 是否其中一个是另一个的子链 若是 就直接返回此结点
		ListNode* cur = pHead1;
		while(cur != nullptr)
		{
			if(cur == pHead2) return cur;
			cur = cur->next;
		}

		cur = pHead2;
		while(cur != nullptr)
		{
			if(cur == pHead1) return cur;
			cur = cur->next;
		}

		// 此外 就两指针 遍历  分3种情况
		if(pHead1 == pHead2)
		{
			return pHead1;
		}
		ListNode* cur1 = pHead1;
		ListNode* cur2 = pHead2;

		while(cur1!=nullptr && cur2!=nullptr)
		{
			if(cur1->next == cur2)
			{
				return cur2;
			}
			else if(cur2->next == cur1)
			{
				return cur1;
			}
			else if(cur1->next == cur2->next ) // && cur1->next!=nullptr  包含了 最后都指向空
			{
				return cur1->next;
			}

			if(cur1->next != nullptr) cur1 = cur1->next;
			
			if(cur2->next != nullptr) cur2 = cur2->next;
		}

		return nullptr;
        
    }

	// // 想明白了得通过 反转链表 从后往前 直到第一个 指针不同时 的位置就是 公共节点

	// ListNode* reverse(ListNode* head)
	// {
	// 	if(head == nullptr) return nullptr;

	// 	ListNode* cur = head;
	// 	ListNode* pre = nullptr;

	// 	while(cur != nullptr)
	// 	{
	// 		ListNode* tmp = cur->next;

	// 		cur->next = pre;

	// 		pre = cur;
	// 		cur = tmp;
	// 	}

	// 	return pre;
	// }

	// ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {

	// 	if(pHead1==nullptr || pHead2==nullptr)
	// 	{
	// 		return nullptr;
	// 	}

	// 	// 反转链表

	// 	ListNode* inv1 = reverse(pHead1); // 也不行  因为 翻转第一个之后 蒂2个的反转就不是那个效果了
	// 	ListNode* inv2 = reverse(pHead2);

	// 	ListNode* cur1 = inv1, *cur2 = inv2;

	// 	// if(cur1 != cur2 ) return nullptr;



	// 	while(cur1->next!=cur2->next)
	// 	{
	// 		cur1 = cur1->next;
	// 		cur2 = cur2->next;

	// 	}

	// 	// 再把 原第一个  转回来
	// 	reverse(inv1);
	// 	return cur1;

	// }

};

O(n) O(1)

虽然是简单题 但 通过率并不高