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

思路一:

暴力反射：拿链表1的第一个节点和链表2下所有节点遍历，然后拿链表1的第二个节点和链表2下的节点比较，以此类推：

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        ListNode firstNode = pHead2;
        for (; pHead1 != null; pHead1 = pHead1.next) {
            if (pHead2 == null) {
                pHead2 = firstNode;
            }
            for (; pHead2 != null; pHead2 = pHead2.next) {
                if (pHead1 == pHead2) {
                    return pHead1;
                }
            }
        }
        return null;
    }

思路二:

一种解决方式就是先把第一个链表的节点全部存放到集合set中，然后遍历第二个链表的每一个节点，判断在集合set中是否存在，如果存在就直接返回这个存在的结点。如果遍历完了，在集合set中还没找到，说明他们没有相交，直接返回null即可

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
         HashSet hashset= new HashSet();
        while(pHead1!=null){
            hashset.add(pHead1);
            pHead1=pHead1.next;
        }
        while(pHead2!=null){
            if(hashset.contains(pHead2)){
                return pHead2;
            }
            pHead2=pHead2.next;
        }
        return null;
    }

思路三:

走A+B 路线。总长相等，步长相等，肯定会相遇‘

import java.util.*;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
       ListNode n1 = pHead1;
        ListNode n2 = pHead2;
        while (n1 != n2) {
            if (n1==null) {
                n1 = pHead2;
            }else{
                n1 = n1.next;
            }
            if (n2==null) {
                n2 = pHead1;
            }else{
                n2 = n2.next;
            }
        } // while不再循环说明 n1和n2 相等
        return n1;
    }
}