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

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) {
        // 左程云老师讲过这道题。分别测量两条链表的长度length1和length2，计算二者的差值diff
        // 先让较长链表走diff个结点，然后二者同时一次走一个结点，相遇的结点就是第一个公共节点

        // 算法的时间复杂度O(N)，额外空间复杂度O(1)

        // 1.分别遍历一遍链表，得到总共有几个结点
        if (pHead1 == null) {
            return null;
        }
        if (pHead2 == null) {
            return null;
        }
        // 确保两个链表都至少有一个结点
        int length1 = 0;
        int length2 = 0;
        ListNode cur = pHead1;
        while (cur != null) {
            length1++;
            cur = cur.next;
        }
        cur = pHead2;
        while (cur != null) {
            length2++;
            cur = cur.next;
        }

        // 2.找到较长的链表并计算差值
        ListNode longListHead = length1 >= length2 ? pHead1 : pHead2;
        ListNode shortListHead = length1 >= length2 ? pHead2 : pHead1;
        int diff = Math.abs(length1 - length2);

        // 3.先让较长链表走diff个结点，然后二者同时一次走一个结点，相遇的结点就是第一个公共节点
        ListNode longListCur = longListHead;
        ListNode shortListCur = shortListHead;
        while(diff > 0) {
            longListCur = longListCur.next;
            diff--;
        }
        // 4.此时，令longListCur和shortListCur同时一次往前走一个结点，直到它们相遇
        while (longListCur != shortListCur) {
            longListCur = longListCur.next;
            shortListCur = shortListCur.next;
        }
        // 5.返回相遇的结点，就是第一个公共结点
        return longListCur;
    }
}