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

**> # 两个链表的第一个公共结点

图解：**

链接

思路：

1.设置两个节点head1和和head2,将两个节点分别位于两个链表头结点处

2.同时出发，一起向相应的链表的后面进行遍历，当两个节点位于同一地址的时候，就是两个链表的第一个公共节点

3.但是如果发现head1已经遍历完链表1,就让它从pHead2开始遍历链表2

** 4.同理：如果head2已经遍历完链表2，就让它从pHead1开始遍历链表1**

** 5.由于它们是同时出发的，所以到相遇的时候经过的时间是一样的，又因为速度也是一样的，所以最后相遇的时候经过的总路程是一样的，而由于是两个表交错着走，所以最后路程一样的位置就是两个链表的两个链表的公共节点**

** 6.如果没有公共节点，随后head1和head2都会走到null,此时head1==head2，会退出循环，返回null**

代码：

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) {
        //设置两个节点head1和和head2,将两个节点分别位于两个链表头结点处
        ListNode head1=pHead1;
        ListNode head2=pHead2;
        //同时出发，一起向相应的链表的后面进行遍历，当两个节点位于同一地址的时候，就是两个链表的第一个公共节点
        //但是如果发现head1已经遍历完链表1,就让它从pHead2开始遍历链表2
        //同理：如果head2已经遍历完链表2，就让它从pHead1开始遍历链表1
        //由于它们是同时出发的，所以到相遇的时候经过的时间是一样的，又因为速度也是一样的，所以最后相遇的时候经过的总路程是一样的，而由于是两个表交错着走，所以最后路程一样的位置就是两个链表的两个链表的公共节点
        //如果没有公共节点，随后head1和head2都会走到null,此时head1==head2，会退出循环，返回null
         while(head1!=head2){
            if(head1==null){
                head1=pHead2;
            }else{
                head1=head1.next;
            }
            if(head2==null){
                 head2=pHead1;
            }else{
                head2=head2.next;
            }
        
         }
         return head1;
    }
}