思路：

题目中的信息：

两个链表含有公共结点或没有，有公共结点则返回第一公共结点指针
单链表，无循环
采用双指针，可以遍历解决，但并非遍历一次

方法一：双指针长度比较法

具体做法：

我们可以通过单独的遍历比较两个链表的长度，得到长度差n，其中较长的链表先动n次指针，然后两链表同步向后，相等之处便是第一个公共结点。图片说明

class Solution {
public:
    int ListLenth( ListNode* pHead){  //计算链表长度的函数
        ListNode* p = pHead;
        int n = 0;
        while(p != NULL){
            n++;
            p = p->next;
        }
        return n;
    }
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        int p1 = ListLenth(pHead1);  
        int p2 = ListLenth(pHead2);
        if(p1 >= p2){            //当链表1更长时，链表1指针先走p1-p2步
            int n = p1 - p2;
            for(int i = 0; i < n; i++){
                pHead1 = pHead1->next;
            }
            while((pHead1 != NULL) && (pHead2 != NULL) && (pHead1 != pHead2)){ //两个链表同时移动，直到有公共结点时停下
                pHead1 = pHead1->next;
                pHead2 = pHead2->next;
            }
        }
        else{      //反之，则链表2先行p2-p1步
            int n = p2 - p1;
            for(int i = 0; i < n; i++){
                pHead2 = pHead2->next;
            }
            while((pHead1 != NULL) && (pHead2 != NULL) && (pHead1 != pHead2)){
                pHead1 = pHead1->next;
                pHead2 = pHead2->next;
            }
        }
        return pHead1;
    }
};

复杂度分析：

时间复杂度：O(n)，其中n为两链表较长者的长度，虽是多次循环，但都为单循环，取最大值即为O(n)
空间复杂度：O(1)，没有其他空间申请

方法二：双指针连接法

具体做法：

由上种方法长度差的思路，不同上述一个指针先走另一个指针后走，仅需将两个链表连在一起，两个指针同步走。易知将两个链表连在一起长度都相等，对于遍历两个链表的两个指针，公共部分走的步数是一样的，非公共部分因都走了两个链表，因此也是相同的，所以绕了一圈，第一个相同的结点便是第一个公共结点。也不需要物理上将两个链表连在一起，仅需指针在一个链表的尾部时直接跳到另一个链表的头部。具体示例可参考图解。图片说明

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        if(!pHead1 || !pHead2)  //其中有一个为空，则不能有公共结点，返回null
            return NULL;
        ListNode* p1 = pHead1;
        ListNode* p2 = pHead2;
        while(p1 != p2)  //相当于遍历两个链表的所有值
        {
            p1 = p1 == NULL ? pHead2 : p1->next;   
            p2 = p2 == NULL ? pHead1 : p2->next;
        }
        return p1;
    }
};

复杂度分析：

时间复杂度：O(n+m)，其中m与n分别为两链表的长度，因一次遍历两链表，所以为O(n+m)
空间复杂度：O(1)

题解 | #两个链表的第一个公共结点#

思路：