/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

// // 算法1：快慢指针 
// class Solution {
// public:
//     ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
//         // 计算长度，作差，快慢指针，判断指向节点是否相等
//         auto a = headA;
//         auto b = headB;
//         int len_a = 0, len_b = 0;
//         while(a){
//             len_a++;
//             a = a->next;
//         }
//         while(b){
//             len_b++;
//             b = b->next;
//         }
//         a = headA;
//         b = headB;
//         if(len_b < len_a) {
//             swap(a,b); // 让b成为快指针
//             swap(len_a,len_b);
//         }
//         int gap = len_b - len_a;
//         while(gap--){
//             b = b->next;
//         }
//         while(a){
//             if(a == b) return a;
//             a = a->next;
//             b = b->next;
//         }
//         return NULL;
//     }
// };

// 算法2：双指针（“循环”指针）
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;
    }
};