两个链表的第一个公共结点

输入两个链表，找出它们的第一个公共结点。

一定是Y型的结构

从末尾开始遍历，如果有不同的，那么前一个节点就是第一个公共节点。

思路，把节点放到栈结构里面，然后进行比较节点。

#include <iostream>
#include <string>
#include<vector>
#include<algorithm>
#include <stack>
using namespace std;


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;

        stack<ListNode *>p1;
        stack<ListNode *>p2;
        ListNode* node = NULL;

        while (pHead1){
            p1.push(pHead1);
            pHead1 = pHead1->next;
        }
        while (pHead2){
            p2.push(pHead2);
            pHead2 = pHead2->next;
        }
        while ((p1.size()>0 && p2.size()>0) && p1.top() == p2.top()){

            cout << p1.top()->val <<"   "<< p2.top()->val << endl;

            node = p1.top();
            p1.pop();
            p2.pop();
            
        }
        return node;
    }
};


int main(){
    Solution s;

    ListNode *pHead1 = new ListNode(1);
    pHead1->next = new ListNode (2);
    pHead1->next->next = new ListNode(3);

    ListNode *pHead2 = new ListNode(1);

    pHead2->next = pHead1->next->next;

    ListNode * node = s.FindFirstCommonNode(pHead1, pHead2);
    if (node)
    cout << node->val << endl;


}