输入两个链表，找出它们的第一个公共结点

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

    分析：第一反应是蛮力法，这是没认真思考才想到的方法。仔细分析就会发现，这两个链表有着共同的尾部，在两个链表达到第一个公共结点后，之后每个结点都是相同的，拓扑形状呈现为Y型结构。

    思路一：首先遍历两个链表，得到两个链表的长度，并得到两个链表的长度差。然后进行第二次遍历，首先在更长的哪一条链表上先走那个长度差的步数（可能长度差为零，一步也不走），然后同步遍历两条链表，直到找到相同的结点，若相同的结点为NULL，说明没有公共节点。

   

//先计算两个链表的长度，然后让长的链表先走两个链表的长度差，
//然后一起走，相同时即得到公共结点，若同为NULL，则表明无公共结点
/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        int length1 = FindLength(pHead1);
        int length2 = FindLength(pHead2);
        if(length1 <= length2){
            pHead2 = GoNSteps(pHead2, length2 - length1);
        }
        else{
            pHead1 = GoNSteps(pHead1, length1 - length2); 
        }
        while(pHead1 != pHead2){
            pHead1 = pHead1 -> next;
            pHead2 = pHead2 -> next;
        }
        return pHead1;
    }

    //计算链表长度
    int FindLength(ListNode* pHead){
        int length = 0;
        while(pHead){
            ++length;
            pHead = pHead -> next;
        }
        return length;
    }

    //前进N个结点
    ListNode* GoNSteps(ListNode* pHead, int n){
        while(n--){
            pHead = pHead -> next;
        }
        return pHead;
    }

};

    思路二：这个比较难想到，直接上代码，然后再分析

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode* p1 = pHead1, * p2 = pHead2;
        while(p1 != p2){
            p1 = (p1 == nullptr ? pHead2 : p1 -> next);
            p2 = (p2 == nullptr ? pHead1 : p2 -> next);
        }
        return p1;
    }
};

            第一种情况：两条链表长度相同且有公共结点，容易得出循环体内第一次就遍历到公共结点；

            第二种情况：长度相同且没有公共结点，走到尾部NULL相遇，返回NULL；

            第三种情况：长度不同有公共结点，第一遍遍历就得到差值，第二遍一起到公共结点；

            第四种情况：长度不同且没有公共结点，第一遍得到差值，第二遍一起到结尾，返回NULL。