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

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
#include <unordered_set>
class Solution {
public:
	// 双指针遍历，遍历完自己的链表就去遍历另一个链表，直到两个指针相遇
	ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
		ListNode* head1 = pHead1;
		ListNode* head2 = pHead2;
		while (pHead1 != pHead2) {
			if (pHead1==nullptr) {
				pHead1 = head1;
			}
			else {
				pHead1 = pHead1->next;
			}
			if(pHead2 == nullptr){
				pHead2 = head2;
			}
			else {
				pHead2 = pHead2->next;
			}

		}
		return pHead1;
	}
	// 哈希表 空间复杂度O（n）
    // ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
    //     unordered_set<ListNode*> hax;
	// 	while (pHead1) {
	// 		hax.insert(pHead1);
	// 		pHead1 = pHead1->next;
	// 	}
	// 	while (hax.count(pHead2)==0 && pHead2) {
	// 		pHead2 = pHead2->next;
	// 	}
	// 	return pHead2;
    // }
};

两个方法

一：双指针法. 使用两个指针同样的速度遍历两个链表，并且当遍历完自己的链表后就去遍历另一个链表，直到两个指针相遇。

二：哈希表法. 首先遍历其中一个链表，并把节点指针保存在哈希表中，当遍历另一个链表时，判断当前节点指针是否已经存在于上述哈希表中，如果是则输出此节点。