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

/*
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 NULL;
	  //先遍历两个链表得到它们的长度
        int n1 = 0, n2 = 0;
        ListNode* node1 = pHead1;
        ListNode* node2 = pHead2;
        while (node1) {
            n1++;
            node1 = node1->next;
        }
        while (node2) {
            n2++;
            node2 = node2->next;
        }
        int n = abs(n1 - n2);
        node1 = pHead1;
        node2 = pHead2;
	  //较长的链表先走长度差值的距离，n更新为较短链表的长度
        if (n1 < n2) {
            while (n--) {
                node2 = node2->next;
            }
            n = n1;
        } else {
            while (n--) {
                node1 = node1->next;
            }
            n = n2;
        }
	  //两个链表指针同时走，如果指向相同说明链表相交
        while (n-- && node1 != node2) {
            node1 = node1->next;
            node2 = node2->next;
        }
        if (node1 == node2) return node1;
        else return NULL;
    }
};