两个链表的第一个公共节点（stack的使用）

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

#include <iostream>
#include <stack>

using namespace std;

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};

//之前这个代码一直通不过的原因是，stack的top操作需要首先检查栈是否为空，如果栈为空，直接去top的话会导致段错误；
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        cout << pHead1 << " " << pHead2 << endl;
        if(pHead1 == NULL || pHead2 == NULL){
            return NULL;
        }
        if(pHead1 == pHead2)
            return pHead1;
        stack<ListNode *> st1,st2;
        while(pHead1 != NULL){
            st1.push(pHead1);
            pHead1 = pHead1->next;
        }
        while(pHead2 != NULL){
            st2.push(pHead2);
            pHead2 = pHead2->next;
        }
        if(st1.top() != st2.top()){ //如果链表最末尾的节点都不相同，那么说明没有公共节点；（该行该函数最后一行搭配）
            return NULL;
        }
        while(st1.size() != 0 && st2.size() != 0 && st1.top() == st2.top()){
            st1.pop();
            st2.pop();
        }
        if(st1.size() == 0) //如果st1先遍历结束，说明st1的第一个节点就是公共节点，也即st2栈顶元素的next指针指向的节点；
            return st2.top()->next;
        else if(st2.size() == 0) //同理，如果st2线遍历结束，说明st2的第一个节点就是公共节点；
            return st1.top()->next;
        else
            return st1.top()->next; //这一行和第34行搭配，如果st1和st2都不为空，但是两栈栈顶元素的值不相等，那么最近栈顶元素的next指针指向的元素就是公共节点；
    }
};

int main()
{
    ListNode n1(1);
    ListNode n2(2);
    n1.next = &n2;

    Solution s;
    cout << &n1 << " " << &n2 << endl;

    ListNode* ret = s.FindFirstCommonNode(&n1, &n2);
    cout << ret << endl;
}

注：
1、所谓链表的第一个公共节点，即一种拓扑形状类似Y型的两个链表（两个链表一开始是分开的，从某一个节点开始汇合为一个链表，并且从这个公共节点开始之后所有的节点都是重合的，因为每个节点只有一个next指针）。
2、判断节点是否为公共节点，只需要判断指向此节点的指针是否相同。注意，不能按照节点中val的值是否相等来判断是否为公共节点。
3、stack的top操作需要先去判断栈是否为空，否则的话会出问题
4、之前我们已经介绍过三种主要的顺序容器，各自是vector、list和deque，这三种顺序容器的设计都会设计到迭代器的概念。STL要求不论什么一种容器都必须内置一个迭代器，假设连迭代器都没有内置，就谈不上”容器“的定义了。所以。stack仅仅是一个容器适配器，并非一个容器，由于stack不提供迭代器，所以在元素不弹出的前提下不可以遍历内部全部的元素。

参考：STL之容器适配器stack的实现框架