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

import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    // 双指针的方法，分别遍历两个链表，当其中任意一个指针到达对应的链表末尾后，重定向到另一个链表的头部
    // 这样可以想象为将连个链表合二为一，不用纠结两个链表长度不一的情况
    // 如果两个链表没有公共结点，则指针会同时到达另一个链表尾部的null的位置
    // 如果有公共节点，则指针会同时到达第一个公共结点
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1 == null || pHead2 == null) return null;

        ListNode node1 = pHead1;
        ListNode node2 = pHead2;
        // 为了满足时间复杂度O(n)，这里不能写node1.next == null，这样没办法结束循环，如果再加入一个判断flag，又会超时
        // 这里写node1 == null（实际上是把null也看成了一个公共结点），则运行node的值为null，则满足了两个指针最终的值一定会相等，直接返回任意一个指针就可以了。
        while(node1 != node2){
            if(node1 == null){
                node1 = pHead2;
            }else{
                node1 = node1.next;
            }
            if(node2 == null){
                node2 = pHead1;
            }else{
                node2 = node2.next;
            }
        }

        return node1;
    }
}