题目描述

如果有公共结点肯定是在后面重叠，且后面部分都是共同的。
方法1：先计算出两个链表的长度，可以让比较长的先走两个链表长度之差的步数，两个再一起走。
方法2：不同部分为a， 和b，公共部分为c；a + c + b = b + c + a;让两个一起走，a走到头就转向b， b走到头转向a，则在公共部分相遇。

C++ 代码

class Solution {
public:
    ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
        auto p = headA, q = headB;
        int la = 0, lb = 0;
        for (auto t = headA; t; t = t->next) la ++;
        for (auto t = headB; t; t = t->next) lb ++;
        int k = la - lb;
        if (la < lb) {
            p = headB, q = headA;
            k = lb - la;
        }
        while(k --) {
            p = p->next;
        }
        while(p) {
            if (p == q) return p;
            p = p->next;
            q = q->next;
        }
        return nullptr;
    }
};

C++ 代码

class Solution {
public:
    ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
        auto p = headA, q = headB;
        while(p != q) {
            if(p) p = p->next;
            else p = headB;
            if (q) q = q->next;
            else q = headA;
        }
        return p;
    }
};