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

链表里面有个指针，指向头结点的指针一般不要动，移动的时候找个替补指针，但是一直纠结，替补指针指向头结点，做了改动，不是照样改变了原链表吗，跪在每K个节点反转那道题了。

• for循环YYDS

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        for(ListNode h1=pHead1;h1!=null;h1=h1.next){
            for(ListNode h2=pHead2;h2!=null;h2=h2.next){
                if(h1 == h2)
                    return h1;
            }
        }
        return null;
    }
}

• 栈，因为题意规定了，相同的数都在最后，所以最后的数不相同时，就结束了,这里最妙的地方在于新的头结点被不断刷新，取到的值就是最新的相同的节点，至于这个节点后面的next，那都是相同的，所以不用纠结next要置为空的情况了

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) {
        ListNode head = null;
        Stack<ListNode> stack1 = pushIn(pHead1);
        Stack<ListNode> stack2 = pushIn(pHead2);
        
        while(!stack1.empty() && !stack2.empty()&&stack1.peek().val == stack2.peek().val){
            head = stack1.pop();
            stack2.pop();
        }
        return head;
    }
    
    public Stack<ListNode> pushIn(ListNode head){
        Stack<ListNode> stack = new Stack<>();
        ListNode cur = head;
        while(cur!=null){
            stack.push(cur);
            cur = cur.next;
        }
        return stack;
    }
}

• set，利用set元素不重复的特性，第一次出现重复的地方就是重合的节点。

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) {
       
         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;
    }
}

• 上面那几个都不满足要求，题目要求空间复杂度为1，现将较长的链表的前面多余部分去掉，两个链表站到同一起跑线，头结点同时后移，知道遇到第一个相等的值就是结果

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) {
        int a=0,b=0;
        ListNode pa = pHead1,pb = pHead2;
        while(pa!=null){
            a++;
            pa = pa.next;
        }
        while(pb!=null){
            b++;
            pb = pb.next;
        }
        
        int c = a-b;
        if(c<0){
            while(c++<0)pHead2 = pHead2.next;
        }else{
            while(c-->0)pHead1 = pHead1.next;
        }
        
        while(pHead1!=pHead2){
            pHead1 = pHead1.next;
            pHead2 = pHead2.next;
        }
        return pHead1;
        
    }
}