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

两个链表的第一个公共结点_牛客题霸_牛客网

跟删除链表中倒数第n个节点的思路大致一样，因为两个链表的第一个公共节点，相当于相交部分的倒数第一个节点

两个链表单独入栈，如果栈顶元素相等，则表示是相交部分的节点，弹出

当栈顶元素不相等了，那么栈顶元素的next节点就是第一个公共节点

同样考虑到假如第一个节点便是公共节点，那么弹出后不存在栈顶元素了，所以各自加一个辅助节点

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        if(pHead1==nullptr || pHead2==nullptr)
        {
            return nullptr;
        }
        stack stk1;
        stack stk2;
        ListNode* dummy1 = new ListNode(0);
        ListNode* dummy2 = new ListNode(1);
        dummy1->next = pHead1;
        dummy2->next = pHead2;
        while(dummy1)
        {
            stk1.push(dummy1);
            dummy1 = dummy1->next;
        }
        while(dummy2)
        {
            stk2.push(dummy2);
            dummy2 = dummy2->next;
        }
        while(!stk1.empty() && !stk2.empty())
        {
            ListNode* node1 = stk1.top();
            ListNode* node2 = stk2.top();
            if(node1==node2)
            {
                stk1.pop();
                stk2.pop();
            }
            else
            {
                return node1->next;
            }
        }
        return nullptr;
    }
};