两个链表的第一个公共结点【Java版】

方法一：朴素对齐法（并列最优）

//本题朴素方法：代码虽长，但易读易懂、效率也同样高
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1 == null || pHead2 == null)return null;//写完之后发现此方法可以省略判空
        int len1 = 0;
        int len2 = 0;
        ListNode p1=pHead1;//测长度
        ListNode p2=pHead2;
        while(p1 != null){
            ++len1;
            p1=p1.next;
        }
        while(p2 != null){
            ++len2;
            p2=p2.next;
        }
        p1=pHead1;//重新初始化
        p2=pHead2;
        if(len1 > len2){
            for(int i=0; i<len1-len2; ++i)p1=p1.next;//长的先跑diff,用于对齐
        }
        if(len1 < len2){
            for(int i=0; i<len2-len1; ++i)p2=p2.next;
        }
        while(p1 != p2){
            p1=p1.next;
            p2=p2.next;
        }
        return p1;
    }
}
//时间复杂度：遍历2*(m+n)-2*common个节点
//时间O(m+n)
//空间O(1)

方法二：双指针法（性能一致，优点是短）

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1 == null || pHead2 == null)return null;//此方法不可省略判空
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        while(p1 != p2){
            p1=p1.next;
            p2=p2.next;
            if(p1 == null && p2 ==null)return null;
            if(p1 == null)p1 = pHead2;//这两行是关键：如果到头了，就从另一个的开头“复活”
            if(p2 == null)p2 = pHead1;
        }
        return p1;
    }
}
//时间复杂度：遍历2*(m+n)-2*common个节点
//时间O(m+n)
//空间O(1)