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

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
#include<stack>
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        stack<ListNode* > stack1;
        stack<ListNode* > stack2;
		ListNode* common = nullptr;
		if (pHead1 == nullptr || pHead2 == nullptr) {
		return nullptr;
		}
		while (pHead1) {
			stack1.push(pHead1);
			pHead1 = pHead1->next;
		}
		while (pHead2) {
			stack2.push(pHead2);
			pHead2 = pHead2->next;
		}	

		int len;
		int num = 0;
		if(stack1.size() <= stack2.size())
			len = stack1.size();
		else
			len = stack2.size();

		for(int i = 0; i < len; i++){
			if(stack1.top() == stack2.top()){
				common = stack1.top(); 
				stack1.pop();
				stack2.pop();
				num	+= 1;
				if(num == len){
					return common;
				}		
			}

		}
		return common;	
    }
};

利用栈的思路解决第一个公共点寻找问题，由于是后进先出，而此问题的关键是两个链表的最后公共部分是相同的。

因此考虑使用两个栈分别存储两个链表，

依次比较两个栈顶的结点是否相同，循环次数为长度较短的栈的尺寸

定义一个临时指针common指向空结点，若栈顶结点相同，则临时指针指向栈顶结点，并且释放两个栈顶

直到栈顶结点不同，说明公共结点已释放完毕，此时common指向的就是第一个公共结点，返回common即可。