剑指 offer 笔记 36 | 两个链表的第一个公共结点

题目描述
输入两个链表，找出它们的第一个公共结点。

输入描述:
题目保证输入的数组中没有的相同的数字

思路分析
1、先得到两个链表的长度，比较知道哪个链表长，以及之间的长度差。

2、第二次遍历，在较长的链表多走若干步，然后同时在两个链表上遍历，找到第一个相同节点就是公共节点。

解释说明：

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
         if(pHead1==null||pHead2==null)
                return null;
            int len1 = getlen(pHead1);//获取链表长度
            int len2 = getlen(pHead2);//同上
            if(len1 > len2){//判断哪个链表长，求出之间的长度差，也就是所谓的「若干步」

                int len=len1-len2;
                while(len-- >0)  // 两个链表同时遍历的起点
                    pHead1=pHead1.next;
     
            }else{
                int len=len2-len1;
                while(len-- >0)
                    pHead2=pHead2.next;
            }
             
            while(pHead1!=null&&pHead2!=null){
                if(pHead1.val==pHead2.val)//若此时的节点相同，则说明是公共节点
                    return pHead1;
                else{
                    pHead1=pHead1.next;
                    pHead2=pHead2.next;
                }
            }
            return null;
        
    }
      public int getlen(ListNode head){//获取链表长度的方法
            int count=0;
            while(head!=null){
                count++;
                head=head.next;
            }
            return count;
}
}

链接：https://www.nowcoder.com/profile/963880/codeBookDetail?submissionId=1515606
来源：牛客网