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

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/

// 采用双指针，因为两个链表前面不同，后面相同
// 假设p1长x1，p2长x2，后面共同长度为y
// 我们让p1指针走x1+y+x2，p2指针走x2+y+x1，走相同路程后的下一个点肯定是y的起点也就是第一个公共节点
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {

        // 当整体为空时，肯定不会有公共点
        if(pHead1 == null || pHead2 == null){
            return null;
        }

        // 由于第二次大循环必定相遇，所以我们将无公共节点的判断条件设在第二个大循环之后（也就是三个小循环）
        int count = 0;

        // 双指针
        ListNode node1 = pHead1;
        ListNode node2 = pHead2;

        // 整体移动
        while(count < 3){

            // 相等，返回
            if(node1 == node2){
                return node1;
            }

            // 移动，若到头，转移到另一条链表
            node1 = node1.next;
            if(node1 == null){
                node1 = pHead2;
                // count小循环++，当count=3时，说明有指针开始了第三次循环，则无公共节点
                count++;
            }

            // 移动，若到头，转移到另一条链表
            node2 = node2.next;
            if(node2 == null){
                node2 = pHead1;
                // count小循环++，当count=3时，说明有指针开始了第三次循环，则无公共节点
                count++;
            }

        }

        // 若未相遇，说明无公共节点
        return null;
 
    }
}