面试题04：找出两个单向链表的第一个公共节点

问题描述：给定两个单向链表，找出它们的第一个公共节点。链表的节点定义如下：

struct ListNode
{
int       Key;
      ListNode*   pNext;
};

ListNode* FindFirstCommonNode(ListNode* list1,ListNode* list2){
    ListNode* pCommon=NULL;
if(list1==NULL || list2==NULL){
return pCommon;
    }
    int len1=0;
    int len2=0;
    ListNode* pNode1=list1;
    ListNode* pNode2=list2;
while(pNode1!=NULL){
        len1++;
        pNode1=pNode1->pNext;
    }
while(pNode2!=NULL){
        len2++;
        pNode2=pNode2->pNext;
    }

    pNode1=list1;
    pNode2=list2;
if(len1<len2){
//Swap(pNode1,pNode2);
        ListNode* temp=pNode1;
        pNode1=pNode2;
        pNode2=temp;
    }
    int m=len1>len2?len1:len2;
    int n=len1>len2?len2:len1;
    for(int i=0;i<m-n;i++){
        pNode1=pNode1->pNext;
    }

while(pNode1!=NULL && pNode1->Key!=pNode2->Kye){
        pNode1=pNode2->pNext;
        pNode2=pNode2->pNext;
    }
    pCommon=pNode1;
return pCommon;
}

下面的待测试

#include <iostream>
using namespace std;

#define NULL 0

struct ListNode
{
      int       Key;
      ListNode*   pNext;
};


ListNode* FindFirstCommonNode(ListNode* list1,ListNode* list2){
    ListNode* pCommon=NULL;
if(list1==NULL || list2==NULL){
return pCommon;
    }
    int len1=0;
    int len2=0;
    ListNode* pNode1=list1;
    ListNode* pNode2=list2;
while(pNode1!=NULL){
        len1++;
        pNode1=pNode1->pNext;
    }
while(pNode2!=NULL){
        len2++;
        pNode2=pNode2->pNext;
    }

    pNode1=list1;
    pNode2=list2;
if(len1<len2){
//Swap(pNode1,pNode2);
        ListNode* temp=pNode1;
        pNode1=pNode2;
        pNode2=temp;
    }
    int m=len1>len2?len1:len2;
    int n=len1>len2?len2:len1;
    for(int i=0;i<m-n;i++){
        pNode1=pNode1->pNext;
    }

while(pNode1!=NULL && pNode1->Key!=pNode2->Key){
        pNode1=pNode2->pNext;
        pNode2=pNode2->pNext;
    }
    pCommon=pNode1;
return pCommon;
}

ListNode* CreateNode(int key,ListNode* next=NULL){
    ListNode* node=new ListNode;
    node->Key=key;
    node->pNext=next;
return node;
}

void PrintList(ListNode* head){
    ListNode* p=head;
while(p!=NULL){
        cout<<p->Key<<ends;
        p=p->pNext;
    }
}


main(){

    ListNode* e=CreateNode(5);
    ListNode* d=CreateNode(4,d);

    ListNode* c1=CreateNode(3,d);
    ListNode* b1=CreateNode(2,c1);
    ListNode* a1=CreateNode(1,b1);

    ListNode* c2=CreateNode(31,d);
    ListNode* b2=CreateNode(21,c2);
    ListNode* a2=CreateNode(11,b2);

// PrintList(a1);
    cout<<endl;
    PrintList(a2);
    cout<<endl;

// ListNode* pcommon=FindFirstCommonNode(a1,a2);
// cout<<pcommon->Key<<endl;


return 0;
}