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

题目：

输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

示例：

输入：{1,2,3},{4,5},{6,7}

返回值：{6,7}

说明：第一个参数{1,2,3}代表是第一个链表非公共部分，第二个参数{4,5}代表是第二个链表非公共部分，最后的{6,7}表示的是2个链表的公共部分这3个参数最后在后台会组装成为2个两个无环的单链表，且是有公共节点的

输入：{1},{2,3},{}

返回值：{}

说明：2个链表没有公共节点 ,返回null，后台打印{}

解题思路：

假设一个链表比另一个链表长K个结点，我们先在长的链表上遍历K个结点，之后再同步遍历，此时我们就能保证同时到达最后一个节点。由于两个链表从第一个公共结点开始到链表的尾结点，这一部分是重合的，因此，他们肯定也是同时到达第一个公共结点的。于是在遍历中，第一个相同的结点就是第一个公共的结点。

根据这一思路，我们先要分别遍历两个链表，得到它们的长度，并求出两个长度之差。在长的链表上先遍历长度之差个结点，之后再同步遍历两个链表，直到找到相同的结点，或者一直到链表结束。

代码示例：

 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @param pHead1 ListNode类 
 * @param pHead2 ListNode类 
 * @return ListNode类
 */
struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here
    if(pHead1 == NULL || pHead2== NULL){
        return NULL;
    }
    struct ListNode *p1 = pHead1;
    struct ListNode *p2 = pHead2;
    int len1=0,len2=0;
    while(p1!=NULL){
        p1 = p1->next;
        len1++;
    }
    while(p2!=NULL){
        p2 = p2->next;
        len2++;
    }
    struct ListNode* longList,*shortList;
    int dist;
    if(len1>len2){
        longList=pHead1;
        shortList=pHead2;
        dist=len1-len2;
    }else{
        longList=pHead2;
        shortList=pHead1;
        dist=len2-len1;
    }
    while(dist--)
        longList=longList->next;
    while(longList!=NULL){
        if(longList==shortList)
            return longList;
        else{
            longList=longList->next;
            shortList=shortList->next;
        }
    }
    return NULL;
}