题目的主要信息：

• 两个无环的单向链表，找出它们的第一个公共结点
• 如果没有公共节点则返回空
• 要求：空间复杂度$O\left(1\right)O(1)$O(1)，时间复杂度$O\left(n\right)O(n)$O(n)

方法一：长度比较法

具体做法：

我们可以分别统计两个链表的长度，然后对于较长的一个链表先走长度之差这么多步，在同步往后遍历，遇到的第一个相同的结点就是第一个公共结点。

public class Solution {
    public int Lenth(ListNode pHead){//计算链表的长度
        ListNode p = pHead;
        int n = 0;
        while(p != null){ //遍历每一个结点
            n++;
            p = p.next;
        }
        return n;
    }
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        int n1 = Lenth(pHead1); 
        int n2 = Lenth(pHead2);
        if(n1 >= n2){ //链表1更长，链表1指针先走n1-n2步
            int n = n1 - n2;
            for(int i = 0; i < n; i++) //链表1先行
                pHead1 = pHead1.next;
            while((pHead1 != null) && (pHead2 != null) && (pHead1 != pHead2)){ //两个链表同时移动，直到有公共结点时停下
                pHead1 = pHead1.next;
                pHead2 = pHead2.next;
            }
        }
        else{ //反之，则链表2先行n2-n1步
            int n = n2 - n1;
            for(int i = 0; i < n; i++)//链表2先行
                pHead2 = pHead2.next;
            while((pHead1 != null) && (pHead2 != null) && (pHead1 != pHead2)){
                pHead1 = pHead1.next;
                pHead2 = pHead2.next;
            }
        }
        return pHead1;
    }
}

复杂度分析：

• 时间复杂度：$O\left(n\right)O(n)$O(n)，其中$nn$n为较长链表的长度，两次统计长度都不会超过$O\left(n\right)O(n)$O(n)，找到第一个公共结点只需遍历一次，不会超过$nn$n个结点
• 空间复杂度：$O\left(1\right)O(1)$O(1)，无额外空间使用

方法二：首尾交叉相接法

具体做法：

我们准备两个指针分别从两个链表头同时出发，每次都往后一步，遇到末尾就连到另一个链表的头部，这样相当于每个指针都遍历了这个交叉链表的所有结点，那么它们相遇的地方一定是交叉的地方，即第一个公共结点。

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1 == null || pHead2 == null)  //其中有一个为空，则不能有公共结点，返回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(m+n)O(m+n)$O(m+n)，其中$mm$m和$nn$n分别是两个链表的长度，相当于遍历两个链表的每个结点
• 空间复杂度：$O\left(1\right)O(1)$O(1)，无额外空间使用