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

/*
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) {
            p1 = p1->next;
            len1++;
        }
        while (p2) {
            p2 = p2->next;
            len2++;
        }

        if (len1 >= len2) {
            int x = len1 - len2;
            while (x) {
                pHead1 = pHead1->next;
                x--;
            }
        } else {
            int x = len2 - len1;
            while (x) {
                pHead2 = pHead2->next;
                x--;
            }
        }

        while (pHead1) {
            if (pHead1 == pHead2) {
                return pHead1;
            } else {
                pHead1 = pHead1->next;
                pHead2 = pHead2->next;
            }

        }
        return NULL;





    }
};

思路：如果存在共同节点，那么必然是在链表尾部就是公共的，我们需要将两个链表对齐。

    while (p1) {
        p1 = p1->next;
        len1++;
    }
    while (p2) {
        p2 = p2->next;
        len2++;
    }

分别计算链表长度，找出长的那个，进行处理，向后移动差值。使他们如果都按步长1向后移动，可以同时结束。这样如果一起向后遍历，当遇到一个公共节点的时候，两个头指针指向一个。当一直移动到最后一个也没有遇到时，说明不存在公共节点。