面试题 52：两个链表的第一个公共节点.md

试题链接：66. 两个链表的第一个公共结点 - AcWing题库

方法一：同步移动

• 思路：让长的部分先移动到和短的同步，然后一起往后遍历，当指向同一个节点时说明找到了第一个公共节点。需要先求两段链表的长度。
• 时间复杂度：O(n)
• 空间复杂度：O(1)

class Solution {
public:
    ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
        if (!headA || !headB) return nullptr;
        
        int lenA = getLength(headA);
        int lenB = getLength(headB);
        
        if (lenA < lenB) swap(headA, headB);
        
        for (int i = 0; i < abs(lenA - lenB); i++) headA = headA->next;
        
        while (headA) {
            if (headA == headB) {
                return headA;
            }
            headA = headA->next;
            headB = headB->next;
        }
        
        return nullptr;
    }
    
    int getLength(ListNode *head) {
        int len = 0;
        while (head) {
            head = head->next;
            len++;
        }
        return len;
    }
};

方法二：距离计算

• 思路：两个链表指针同时移动，当有一个指针为空时这个指针重新从相对的那条链表上移动，可以发现两者走的总距离的相等的，且会在相交点重合，如果没有重合，那么他们都会是指向空。
• 时间复杂度：O(n)
• 空间复杂度：O(1)

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