剑指offer52:两个链表的第一个公共节点

题目:输入两个链表,找出它们的第一个公共结点

思路:暴力法时间复杂度O(n^2). 当两个链表具有公共节点时,第一个公共节点之后的节点全部相等. 若从后向前比较,当比较到第一个不相等的节点后,其下一个节点即为公共节点. 使用两个栈保存链表,然后依次取两个栈顶节点比较.

ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        if(pHead1==nullptr ||  pHead2==nullptr)
            return nullptr;;
        stack<ListNode*> st1;
        stack<ListNode*> st2;
        ListNode* cur=nullptr;
        while(pHead1!=nullptr){
            st1.push(pHead1);
            pHead1=pHead1->next;
        }
        while(pHead2!=nullptr){
            st2.push(pHead2);
            pHead2=pHead2->next;
        }
        while(!st1.empty() && !st2.empty()){
            ListNode* node1=st1.top();
            st1.pop();
            ListNode* node2=st2.top();
            st2.pop();
            if(node1->val==node2->val)
                cur=node1;
        }

    return cur;
    }