【剑指offer】面试题37：两个链表的第一个公共结点

题目：

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

思路：

由链表的定义知是单链表。对于单链表，如果两个链表有公共结点，则两个链表必然是像Y型相交。则先计算出各个链表的长度，让长链表的头指针先走多出来的几步，再同时让两个链表的指针移动，则判断两个指针是否相等即可。

代码：

/*

struct ListNode {

    int val;

    struct ListNode *next;

    ListNode(int x) :

            val(x), next(NULL) {

    }

};*/

class Solution {

public:

    ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2) {

        if(pHead1==NULL || pHead2==NULL)  return NULL;

        int len1=GetListLength(pHead1);

        int len2=GetListLength(pHead2);

        int diff=len1-len2;

        ListNode* head1=pHead1;

        ListNode* head2=pHead2;

        if(diff>)

        {

            head1=GoNStep(pHead1,diff);

        }

        else

            head2=GoNStep(pHead2,-diff);

        while(head1!=NULL)

        {

            if(head1==head2)  return head1;

            head1=head1->next;

            head2=head2->next;

        }

        return NULL;

    }

private:

    ListNode* GoNStep(ListNode *pHead, int n)

    {

        for(int i=;i<n;++i)

            if(pHead)  pHead=pHead->next;

        return pHead;

    }

    int GetListLength(ListNode *pHead)

    {

        int len=;

        while(pHead!=NULL)

        {

            len++;

            pHead=pHead->next;

        }

        return len;

    }

};