52.两个链表的第一个公共结点（简单）

考点：本题考查时间空间效率的平衡

题目描述

输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

思路：

如果两个链表有公共结点，那么公共结点出现在两个链表的尾部，如果从两个链表的尾部开始往前比较，那么最后一个相同的结点就是要找的结点。首先遍历两个链表得到他们的长度，在第二次遍历的时候，在较长的链表上先走若干步，接着同时在两个链表上遍历，找到的第一个相同的结点就是它们的第一个公共结点。

/*
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 len1 = getLength(pHead1);
        int len2 = getLength(pHead2);
        if(len2>len1){
            int len = len2 - len1;
            //先在长链表上走几步，再同时在两个链表上遍历
            for(int i=0;i<len;i++){
                pHead2 = pHead2.next;
            }
        }
        else{
            int len = len1 - len2;
            for(int i=0;i<len;i++){
                pHead1 = pHead1.next;
            }
        }
        while(pHead1 != null && pHead2 != null){
            if(pHead1 == pHead2){
                //第一个公共结点
                ListNode res = pHead1;
                return res;
            }
            pHead1 = pHead1.next;
            pHead2 = pHead2.next;
        }
        return null;
    }
    
    //获得本链表的长度
    private int getLength(ListNode headNode){
        int length = 0;
        ListNode tmpNode = headNode;
        while(tmpNode!=null){
            length++;
            tmpNode = tmpNode.next;
        }
        return length;
    }
}

如果链表的长度分别为m，n，那么时间复杂度为O(m+n)