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

基本思路

题目要找的公共节点是指两个链表中节点引用相同的节点，而不是节点值相同的节点，因此我们要比较的是两个链表的节点引用是否相等来判断是否有公共节点。

由于两个链表长度不一致，一般需要先将长链表遍历到剩余长度和短链表相同的长度再逐个比较，但是可以将两个链表拼接起来循环遍历，如果链表A遍历结束后就遍历链表B，链表B遍历结束后就遍历链表A，这样两个的长度是相等的，可以同时遍历，如果有公共节点就找到后返回，如果没有公共节点两个链表都会同时返回null，此时返回null即可。

参考

参考题解-1

参考题解2

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;
        }
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        while (p1 != p2) {  // 比较的是两个节点的引用，如果相等说明是公共节点，后续节点都是相同的，如果没有公共节点，p1和p2会同时达到null，此时也是相等的，会跳出循环，只不过后面返回的p1是null
            p1 = p1.next;
            p2 = p2.next;

            if (p1 != p2) {  // 如果其中一个链表达到末尾，换成另外一个链表开头遍历，这相当于将两个链表拼接起来遍历了，保证遍历的长度是相同的
                if (p1 == null) {
                    p1 = pHead2;
                }
                if (p2 == null) {
                    p2 = pHead1;
                }
            }
        }

        return p1;
    }
}