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

从题目中可以看到，公共结点都是插入在不同结点之后的。所以先遍历两个链表得到链表长度，将长链表的后指针后移，直至两链表长度相等，然后比较两链表头指针，相等则返回，不等则同时后移一位,最终可得结果。 这样做最多只有一重循环，时间复杂度为O(n)。 只使用了两个临时变量保存用于遍历的指针，两个临时变量用于保存链表长度，空间复杂度为O(1)。 之所以不用集合来存放结点的方式做，是因为集合会使空间复杂度变为O(n)，不符合题意。

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode* p1 = pHead1;
        ListNode* p2 = pHead2;
        int len1 = 0;
        int len2 = 0;
        while(p1){
            len1++;
            p1 = p1->next;
        }
        while(p2){
            len2++;
            p2 = p2->next;
        }
        if(len1 > len2){
            int count = len1 - len2;
            for(int i = count;i > 0;i--){
                pHead1 = pHead1->next;
            }
        }
        else if(len1 < len2){
            int count = len2 - len1;
            for(int i = count;i > 0;i--){
                pHead2 = pHead2->next;
            }
        }
        while(pHead1 && pHead2){
            if(pHead1 == pHead2){
                return pHead1;
            }
            pHead1 = pHead1->next;
            pHead2 = pHead2->next;
        }
        return nullptr;
    }
};