剑指offer 两个链表的第一个公共节点

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        // 初始条件
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        // 分别求出两个链表的长度
        int length1 = 0;
        int length2 = 0;
        for (ListNode h1 = pHead1; h1 != null; h1 = h1.next) {
            ++length1;
        }
        for (ListNode h2 = pHead2; h2 != null; h2 = h2.next) {
            ++length2;
        }
        
        // 先遍历长的链表，等遍历到两个链表一样长的时候，再两个链表一起遍历
        while (length1 != length2) {
            if (length1 > length2) {
                pHead1 = pHead1.next;
                --length1;
            } else {
                pHead2 = pHead2.next;
                --length2;
            }
        }
        
        // 两个链表同时遍历，直到找到公共节点
        while (pHead1 != null && pHead2 != null) {
            if (pHead1.val == pHead2.val) {
                return pHead1;
            }
            pHead1 = pHead1.next;
            pHead2 = pHead2.next;
        }
        
        
        // 到结束还未找到，返回null
        return null;
    }
}