线性复杂度查找链表的公共节点

题目详情：输入两个链表，找出它们的第一个公共结点。
思路：

• 1，由于从公共节点开始之后都是公共节点，也就是说不管两个链的长度是否一样，反过来的公共长度一定一样，于是用两个栈来从后往前匹配，找到最后一个公共节点即为原链的第一个公共节点。
• 2，和思路一很类似，先让两个开始匹配的指针水平线相同，也就是长的那个要走到与短的那个链有相同长度的位置，之后就从前往后匹配。之所以这样子做是因为： $假设k为公共长度,t1为链1的非公共长度，t2为链2的非公共长度，那么s1=t1+k,s2=t2+k,则长的那个移动的偏移量=\mid s1-s2\mid =\mid t1-t2\mid ,说明不会动到公共部分k，所以在这个位置往后找不影响结果。$假设k为公共长度,t1为链1的非公共长度，t2为链2的非公共长度，那么s1=t1+k,s2=t2+k,则长的那个移动的偏移量=∣s1−s2∣=∣t1−t2∣,说明不会动到公共部分k，所以在这个位置往后找不影响结果。
• 3，假设有公共部分，那么公共部分一定在最尾部，把链1链2分别叠加到一块，则有 $s1=s1+s2,s2=s2+s1,处理后s1=s2$s1=s1+s2,s2=s2+s1,处理后s1=s2，然后直接从前往后匹配处理后的串，最终一定回匹配到后面对齐的公共部分。

以上三个思路的复杂度都是 $O(n+m)$O(n+m)，关键都是发现尾部从第一个公共节点开始之后都相等这个特点，这个方法同样可以拓展到多个链表找公共节点

Code：

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        //法一:
        //4ms
        stack<ListNode*> stk1, stk2;
        ListNode* pub = NULL;
        while (!stk1.empty()) stk1.pop();
        while (!stk2.empty()) stk2.pop();
        while (pHead1) {
            stk1.push(pHead1);
            pHead1=pHead1->next;
        }
        while (pHead2) {
            stk2.push(pHead2);
            pHead2=pHead2->next;
        }
        while (!stk1.empty() && !stk2.empty()) {
          if (stk1.top() != stk2.top()) break;
          pub = stk1.top();
          stk1.pop();
          stk2.pop();
        }
        while (!stk1.empty()) stk1.pop();
        while (!stk2.empty()) stk2.pop();
        return pub;

        //法二：
        //3ms
        int len1 = 0, len2 = 0, k;
        ListNode* p = pHead1;
        ListNode* q = pHead2;
        while (p) len1++, p = p->next;
        while (q) len2++, q = q->next;
        if (len1 > len2) {
            k = len1 - len2;
            while (k--) pHead1 = pHead1->next; 
        } else if (len2 > len1) {
            k = len2 - len1;
            while (k--) pHead2 = pHead2->next; 
        }
        while (pHead1) {
            if (pHead1 == pHead2) break;
            pHead1 = pHead1->next;
            pHead2 = pHead2->next;
        }
        return pHead1;

        //法三：
        //3ms
        ListNode* p = pHead1;
        ListNode* q = pHead2;
        while (p != q) {
            p = p ? p->next : pHead2;
            q = q ? q->next : pHead1;
        }
        return p;
    }
};