剑指offer 54- 两个链表的第一个公共结点

输入两个链表，找出它们的第一个公共结点。

当不存在公共节点时，返回空节点。
样例

给出两个链表如下所示：
A：        a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

输出第一个公共节点c1

分析：
算法1：
先计算出两个链表的长度，可以让比较长的先走两个链表长度之差的步数，两个再一起走
时间复杂度：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {      
        auto p = headA, q = headB;
        int la = 0, lb = 0;
        for(auto a = headA; a; a = a->next) la++;
        for(auto b = headB; b; b = b->next) lb++;
        int k = la - lb;
        if(la < lb) k = lb - la, p = headB, q = headA;
        while(k--) p = p->next;
        while(p) {
            if(p == q) return p;
            p = p->next;
            q = q->next;
        }
        return nullptr;
    }
};

算法2：
不同部分为a， 和b，公共部分为c；a + c + b = b + c + a;让两个一起走，a走到头就转向b， b走到头转向a，则在公共部分相遇
时间复杂度：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
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;
    }
};