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

遍历法

首先将两个链表中的结点分别存到两个vector中，看最后一个结点值是否相等，若不相等，则没有公共结点；若相等，则从后往前遍历，直到遇到不相等的结点，此时上一个遍历的结点即为第一个公共结点。

C++代码：

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        if (!pHead1 || !pHead2) {return NULL;}
        vector<ListNode *> a, b;
        while (pHead1) {
            a.push_back(pHead1);
            pHead1 = pHead1->next;
        }
        while (pHead2) {
            b.push_back(pHead2);
            pHead2 = pHead2->next;
        }
        if (a[a.size() - 1]->val != b[b.size() - 1]->val) return NULL;
        int i = a.size() - 2, j = b.size() - 2;
        for (; i >= 0 && j >= 0; i--, j--) {
            if (a[i]->val != b[j]->val) {
                return a[i + 1];
            }
        }
        return i == -1 ? a[0] : b[0];
    }
};

时间复杂度：O(max(m, n)), m，n分别为链表A，B的长度。

空间复杂度：O(n + m)。

双指针法

用两个指针分别遍历两个链表，当走到头的时候，再从另一个链表头开始，巧妙实现两个指针遍历长度相等，遇到的第一个相同的结点即为公共结点。以下图片为官方题解的示意图：

C++代码：

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode *ta = pHead1, *tb = pHead2;
        while (ta != tb) {
            ta = ta ? ta->next : pHead2;
            tb = tb ? tb->next : pHead1;
        }
        return ta;
    }
};