两个单向链表的第一个公共节点

参考

http://blog.163.com/clevertanglei900@126/blog/static/1113522592011914148467/

问题：

两个单向链表，可能存在公共节点。如何判断是否存在公共节点，并找出它们的第一个公共结点。

思想：

1. 如果两个链表相交，则从相交点开始，后面的节点都相同，即最后一个节点肯定相同；
2. 从头到尾遍历两个链表，并记录链表长度，当二者的尾节点不同，则二者肯定不相交；
3. 尾节点相同，如果A长为LA，B为LB，如果LA>LB,则A前LA-LB个先跳过，

   然后二者一起向后遍历，直到遇到相同的节点；LA<LB类似处理
   因为第一个公共节点距起始节点的距离start_a满足： LA - start_a == LB - start_b。

 

const ListNode* FirstCommonNode(const ListNode* listA, const ListNode* listB)
{
    if(listA==NULL || listB==NULL) return NULL;
    int LA=1,LB=1;//A，B链表长度
    const ListNode* curA = listA, *curB = listB;
    //二表节点首地址
    while(curA->next)//求A尾节点，LA长度
    {++LA; curA = curA->next;}
    while(curB->next)//求B尾节点，LB长度
    {++LB; curB = curB->next;}
    if(curA != curB) return NULL;//尾节点不相同，则没有相交
    //重新获取ab的首地址
    curA = listA;curB = listB;
    if(LA > LB)//
    {
        for(int i=0; i<LA-LB; ++i)
            curA = curA->next;//A移到公共节点
    }
    else
    {
        for(int i=0; i<LB-LA; ++i)
            curB = curB->next;//B移到公共节点
    }
    while(curA && curA!=curB)
    {
        curA = curA->next;//不相等就往下走
        curB = curB->next;
    }
    return curA;//返回首个相同的节点
}
 
简单测试代码：
void CreateJointList(const string* strA, int sizeA,const string* strB ,int sizeB,
    const string* strC,int sizeC,ListNode** listA,ListNode** listB)//创建两个相交的链表
{
    ListNode* rootA = new ListNode(strA[0]);
    //数组的第一个元素根节点
    ListNode* rootB = new ListNode(strB[0]);
    *listA = rootA; *listB = rootB;
    //连接
    for(int i=1; i<sizeA; ++i)
    {
        rootA->next = new ListNode(strA[i]);
        rootA = rootA->next;
    }
    for(int i=1; i<sizeB; ++i)
    {
        rootB->next = new ListNode(strB[i]);
        rootB = rootB->next;
    }
    ListNode* tmp = new ListNode(strC[0]);
    rootA->next = tmp;
    rootB->next = tmp;
    for(int i=1; i<sizeC; ++i)
    {
        tmp->next = new ListNode(strC[i]);
        tmp = tmp->next;
    }
}
    ListNode *headA,*headB;
    const int SizeA = 6,SizeB = 7,SizeC = 5;
    const string A[SizeA] = {"I","am","an","List","named","A"};
    //常量数组
    const string B[SizeB] = {"I","am","also","an","List","named","B"};
    const string C[SizeC] = {"this","part","is","in","Comman"};
    //创建交叉链表
    CreateJointList(A,SizeA,B,SizeB,C,SizeC,&headA,&headB);
    //打印A
    PrintList(headA);
    PrintList(headB);
    //找到交点
    const ListNode *node = FirstCommonNode(headA, headB);
    if(node != NULL)
        cout<<"\nCommon Node : \t"<<node->value<<endl;