//得到两个链表第一个公共节点并返回

#include <iostream>
#include<stdio.h>
using namespace std;
typedef struct ListNode{
    int m_nValue;
    ListNode* m_pNext;
}ListNode, *List;//必须是一个链表


void Insert(List& pHead,int data){
    ListNode* p=new ListNode;
    p->m_nValue=data;
    p->m_pNext=NULL;
    if(pHead==NULL)
        pHead=p;
    else{
        p->m_pNext=pHead;
        pHead=p;
    }

}
void Print(List& pHead){
    if(pHead==NULL)
        return ;
    ListNode* p=pHead;
    while(p){
        cout<<p->m_nValue<<" ";
        p=p->m_pNext;
    }
    cout<<endl;
}

unsigned int GetListLength(ListNode* pHead);

int FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2)
{
    // 得到两个链表的长度
    unsigned int nLength1 = GetListLength(pHead1);
    unsigned int nLength2 = GetListLength(pHead2);
    int nLengthDif = nLength1 - nLength2;

    ListNode* pListHeadLong = pHead1;
    ListNode* pListHeadShort = pHead2;
    if(nLength2 > nLength1)
    {
        pListHeadLong = pHead2;
        pListHeadShort = pHead1;
        nLengthDif = nLength2 - nLength1;
    }

    // 先在长链表上走几步，再同时在两个链表上遍历
    for(int i = 0; i < nLengthDif; ++ i)
        pListHeadLong = pListHeadLong->m_pNext;

    while((pListHeadLong != NULL) &&
        (pListHeadShort != NULL) &&
        (pListHeadLong->m_nValue != pListHeadShort->m_nValue))
    {
        pListHeadLong = pListHeadLong->m_pNext;
        pListHeadShort = pListHeadShort->m_pNext;
    }
    if(!pListHeadLong && !pListHeadShort)//没有公共节点

        return 0;
    if(pListHeadLong->m_nValue == pListHeadShort->m_nValue){
        ListNode* pFisrtCommonNode = pListHeadLong;// 得到第一个公共结点
        return pFisrtCommonNode->m_nValue;
    }


}

unsigned int GetListLength(ListNode* pHead)
{
    unsigned int nLength = 0;
    ListNode* pNode = pHead;
    while(pNode != NULL)
    {
        ++ nLength;
        pNode = pNode->m_pNext;
    }

    return nLength;
}

int main()
{
    List l1=NULL;
    Insert(l1,7);
    Insert(l1,6);
    Insert(l1,3);
    Insert(l1,2);
    Insert(l1,1);
    Print(l1);


    List l2=NULL;
    Insert(l2,7);
    Insert(l2,7);
    Insert(l2,5);
    Insert(l2,4);
    Print(l2);
    int tmp=FindFirstCommonNode(l1,l2);
    cout<<tmp;
    return 0;
}