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

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
/*
1.暴力循环，分别循环pHead1,pHead2两个链表
        for(ListNode temp1=pHead1;temp1!=null;temp1=temp1.next){
            for(ListNode temp2=pHead2;temp2!=null;temp2=temp2.next){
                if(temp1==temp2) return temp1;
            }
        }
        return null;
        
        
2.栈解法，从后往前找
    1,先将链表分别存入两个栈中stack1，stack2
    2，当栈不为空，且栈顶相等时，分别出栈，并ListNode ans保存一个出栈元素
    3，结束时，ans保存为第一个相等的元素，返回
/*
import java.util.*;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
            Stack<ListNode> stack1=new Stack<>(); 
            Stack<ListNode> stack2=new Stack<>(); 
        //添加链表到栈中
        while(pHead1!=null){
            stack1.push(pHead1);
            pHead1=pHead1.next;
        }
        
        while(pHead2!=null){
            stack2.push(pHead2);
            pHead2=pHead2.next;
        }
        
        ListNode ans=null;
        while(!stack1.isEmpty() && !stack2.isEmpty() && stack1.peek()==stack2.peek() ){
            //栈不为空，且栈顶相等
            ans=stack1.pop();
            stack2.pop();
        }
        return ans; 
    }
}

3.set 解法,
    1.先将第一个链表保存在set中，set不能报相同元素
    2.判断第二个链表中是否有相同元素，无则继续遍历，有则返回
    import java.util.*;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
          Set<ListNode> set=new HashSet<>(); 
        while(pHead1!=null){
            set.add(pHead1);
            pHead1=pHead1.next;
        }
        while(pHead2!=null && !set.contains(pHead2)){
            pHead2=pHead2.next;
        }
        return pHead2;
        
    }
}

3.差值法
由于两条链表在相交节点后面的部分完全相同，因此我们可以先对两条链表进行遍历
分别得到两条链表的长度，并计算差值 d。让长度较长的链表先走 d 步，然后两条链表同时走，
第一个相同的节点即是节点。

    import java.util.*;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
       //定义链表1的长度为c1，链表2的长度为c2，并分别计算其长度
        int c1=0,c2=0;
        ListNode a=pHead1,b=pHead2;//定义辅助结点遍历长度
        while(a!=null) {
            a=a.next;
            c1++;
        }
        while(b!=null) {
            b=b.next;
            c2++;
        }
        int d=c1-c2;//差值
        if(d>0){//长的先走差值步
            while(d-->0) pHead1=pHead1.next;
        }else{
            d=-d;
            while(d-->0) pHead2=pHead2.next;
        }
        //长的先走完d步后，两者同时走，相同则为入口
        while(pHead1!=pHead2){
            pHead1=pHead1.next;
            pHead2=pHead2.next;
        }
         return pHead2;//返回皆可
         
    }
}
*/

import java.util.*;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
       //定义链表1的长度为c1，链表2的长度为c2，并分别计算其长度
        int c1=0,c2=0;
        ListNode a=pHead1,b=pHead2;//定义辅助结点遍历长度
        while(a!=null) {
            a=a.next;
            c1++;
        }
        while(b!=null) {
            b=b.next;
            c2++;
        }
        int d=c1-c2;//差值
        if(d>0){//长的先走差值步
            while(d-->0) pHead1=pHead1.next;
        }else{
            d=-d;
            while(d-->0) pHead2=pHead2.next;
        }
        //长的先走完d步后，两者同时走，相同则为入口
        while(pHead1!=pHead2){
            pHead1=pHead1.next;
            pHead2=pHead2.next;
        }
         return pHead2;//返回皆可
         
    }
}