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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
  public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
		// 只要有一条链表为空则表示没有公共结点
		if (pHead1 == nullptr || pHead2 == nullptr) {
			return nullptr;
		}

        int len1 = 0, len2 = 0;
        ListNode* p = pHead1;
        ListNode* q = pHead2;
		// 分别计算两条链表的长度
        while (p != nullptr) {
            p = p->next;
            len1++;
        }
        p = pHead1;
        while (q != nullptr) {
            q = q->next;
            len2++;
        }
        q = pHead2;

		// 较长的链表中的指针提前走，直到两个链表剩下的长度相等
        int k = 0;
        if (len1 >= len2) {
            while (k < (len1 - len2)) {
                p = p->next;
                ++k;
            }
        } else {
            while (k < (len2 - len1)) {
                q = q->next;
                ++k;
            }
        }

		// 找到相交的节点并返回
        while (p != nullptr) {
            if (p == q) {
                return p;
            }
            p = p->next;
            q = q->next;
        }

		// 未找到返回空结点
        return nullptr;
    }
};