剑指offer36-两个链表的第一个公共结点

/*
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==NULL || pHead2==NULL)
            return NULL;
        stack<ListNode*> stack1;
        stack<ListNode*> stack2;
        //将链表1放入栈中
        while(pHead1!=NULL){
            stack1.push(pHead1);
            pHead1 = pHead1->next;
        }
        //将链表2放入栈中
        while(pHead2!=NULL){
            stack2.push(pHead2);
            pHead2 = pHead2->next;
        }
        //两个栈同时往外出
        ListNode* p = stack1.top();
        ListNode* q = stack2.top();
        ListNode* result = NULL;
        while(!stack1.empty() && !stack2.empty()){
            p = stack1.top();
            q = stack2.top();
            if(p->val == q->val){
                result = stack1.top();
                stack1.pop();
                stack2.pop();
            }
            else{
                break;
            }
        }
        return result;
        
    }
};