题解 | #两个链表的第一个公共结点#

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
  public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        /*
            将两个输入的链表倒序，比较，第一个值不相同的节点的next就是第一个公共节点
        */

        // 空的判断
        if (pHead1 == nullptr || pHead2 == nullptr) {
            return nullptr;
        }

        std::vector<int> vec1;
        std::vector<int> vec2;
        ListNode* pIndex = pHead1;

        for (int i = 0; pIndex != nullptr; i++) {
            vec1.push_back(pIndex->val);
            pIndex = pIndex->next;
        }
        pIndex = pHead2;
        for (int j = 0; pIndex != nullptr; j++) {
            vec2.push_back(pIndex->val);
            pIndex = pIndex->next;
        }

        int count = 0;
        std::reverse(vec1.begin(), vec1.end());
        std::reverse(vec2.begin(), vec2.end());
        if (vec1.size() <
                vec2.size()) { // 取小的，把小的比完了还没有重复的
            count = vec1.size();
        } else {
            count = vec2.size();
        }

        for (int k = 0; k < count; k++) {
            if (vec1[k] != vec2[k]) {
                // 找到了倒序不同的节点  此时的count还未++
                pIndex = pHead1;
                for (int i = 0; i < vec1.size() - k; i++) {
                    pIndex = pIndex->next;
                }

                ListNode* commonNode = pIndex;
                return commonNode;
            }
        }

        // 运行到了这里说明 至少有一个链表已经遍历完了，但仍没有找到不同的节点。说明二者是包含关系，应该返回整个短的链表
        if (vec1.size() < vec2.size()) {
            return pHead1;
        } else return pHead2;
    }
};