算法1

(栈) $O(m+n)$

剑指offer上用两个辅助栈实现代码如下

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
        if(!headA || !headB) return nullptr;
        stack<ListNode *> stackA;
        stack<ListNode *> stackB;
        ListNode *cur = nullptr;


        while(headA) {
            stackA.push(headA);
            headA = headA->next;
        }
        while(headB) {
            stackB.push(headB);
            headB = headB->next;
        }

        while(stackA.size() && stackB.size()){
            ListNode *prtA = stackA.top(); 
            ListNode *prtB = stackB.top();

            if(prtA == prtB){
                cur = prtB;
                stackA.pop();
                stackB.pop();
            }
            else break;
        }
        return cur;
    }
};