4/21剑指offer

1.两个链表的第一个公共节点
思路：首先遍历两个链表得到他们的长度，就能知道哪个链表比较长，以及长的链表比短的链表多几个节点。在第二次遍历的时候，在较长的链表上先走若干步，接着同时在两个链表上遍历，找到的第一个相同的节点就是他们的第一个公共节点。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        int len1=GetLen(pHead1);
        int len2=GetLen(pHead2);
        int num=len1-len2;//假设1比2长
        ListNode *pLong=pHead1;
        ListNode *pShort=pHead2;
        if(len1<len2)
        {
            num=len2-len1;
            pLong=pHead2;
            pShort=pHead1;
        }
        for(int i=0;i<num;i++)
        {
            pLong=pLong->next;//长链表先走num步
        }
        while((pLong!=nullptr)&&(pShort!=nullptr)&&(pLong->val!=pShort->val))
        {
            pLong=pLong->next;
            pShort=pShort->next;
        }
        return pLong;

    }
    int GetLen(ListNode* Head)//求链表长度的函数
    {
        int len=0;
        ListNode *p=Head;
        while(p!=nullptr)
        {
            len++;
            p=p->next;
        }
        return len;
    }
};