JZ52：两个链表的第一个公共结点

题目链接：JZ52：两个链表的第一个公共结点
题目描述：
输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。
数据范围： n ≤ le ≤ 1000
要求：空间复杂度 O ( 1 ) O(1) O(1)，时间复杂度 O ( n ) O(n) O(n)
题目分析：
① 根据两个链表的长度差，让链表长的一方先走双方的差值步，之后再一起走！两个结点相同，即为两个链表的第一个公共结点。
时间复杂度O(m+n) 需要遍历两个链表
空间复杂度O(1) 没有借助额外的内存空间

import java.util.*;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
       //统计两个链表各自的长度
        int len1 = length(pHead1);
        int len2 = length(pHead2);
        //如果两个链表长度不一，让链表长的一方走两者差值步
        while(len1!=len2){
            if(len1>len2){
                pHead1 = pHead1.next;
                len1--;
            }else{
                pHead2 = pHead2.next;
                len2--;
            }
        }
        //如果两个链表结点相同，则为第一个公共结点
        while(pHead1!=pHead2){
            pHead1 = pHead1.next;
            pHead2 = pHead2.next;
        }
        //返回pHead1 或者 pHead2 任意一个即可！
        return pHead1;
    }
   
    //统计两个链表的长度
    public int length(ListNode node){
        int count = 0;
        while(node!=null){
            count++;
            node = node.next;
        }
        return count;
    }
}

② 双指针法：循环往前走！pHead1 和 pHead2 一定会在相同位置同时出发！它们就会相遇到一点，即第一个公共结点。
时间复杂度O(m+n) 遍历有限次链表
空间复杂度O(1)

import java.util.*;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode a = pHead1;
        ListNode b = pHead2;
        while(a!=b){
            //a如果为null;就让a指向pHead1重新开始遍历链表
            a=(a==null)?pHead1:a.next;
            b=(b==null)?pHead2:b.next;
        }
        return a;
    }
}

③Set集合去重，遇到第一个重复的元素就是公共元素。
时间复杂度O(m+n), 空间复杂度O(m),需要额外存储Set集合空间pHead1链表的大小m

import java.util.*;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        Set set = new HashSet<>();
        while(pHead1!=null){
            set.add(pHead1);
            pHead1 = pHead1.next;
        }
        while(pHead2!=null){
            if(set.contains(pHead2)){
                return pHead2;
            }
            set.add(pHead2);
            pHead2 = pHead2.next;
        }
        return null;
    }
}

总结：面试必考！重点看看！重点掌握第1和2种方法。