52 两个链表的第一个公共结点

牛客

描述

输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

使用双指针，如果指导结尾，则从另一个链表的头开始。这样两个指针会在公共节点相遇。如果没有公共节点，两个指针第二次遍历会同时为空。时间复杂度 o(n) ，空间复杂度 o(1)

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    if(pHead1==null || pHead2==null) return null;
    ListNode p1=pHead1;
    ListNode p2=pHead2;
    while(true){
        if(p1==p2) return p1;
        if(p1.next==null && p2.next==null) return null;
        if(p1.next==null) p1=pHead2;
        else p1=p1.next;
        if(p2.next==null) p2=pHead1;
        else p2=p2.next;
    }
        
}