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

import java.util.*;
/*
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 len1 = 0;
        int len2 = 0;

        ListNode cur1 = pHead1;
        ListNode cur2 = pHead2;
        while(cur1 != null) {
            len1++;
            cur1 = cur1.next;
        }
        while(cur2 != null) {
            len2++;
            cur2 = cur2.next;
        }

	  	// fast 指向pHead1、pHead2 中较长的链表
        ListNode fast = len1 - len2 >= 0 ? pHead1 : pHead2;
	  	// slow 指向pHead1、pHead2 中较短的链表
        ListNode slow = fast == pHead1 ? pHead2 : pHead1;
		// 记录两个链表的长度之差，也就是较长的链表需要先走的步数
        int jump = Math.abs(len1 - len2);
		// 较长的链表先走
        while(jump > 0) {
            fast = fast.next;
            jump--;
        }

	  	// 两个链表这个时候应该一样长了，一起走，相遇即为相交点
        while(fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}