首页 > 代码库 > 两个链表的第一个公共结点

两个链表的第一个公共结点

题目:输入两个链表,找出他们的第一个公共结点。链表定义如下:

struct ListNode
{
    int m_nKey;
    ListNode* m_pNext;
};

分析:方法一,蛮力法。在第一链表上顺序遍历每个结点,每遍历到一个结点的时候,在第二个链表上顺序遍历每个结点。如果在第二个链表上有一个结点和第一个链表上的结点一样,说明两个链表在这个节点上重合,于是就找到了第一个公共结点,时间复杂度为O(mn),m,n为两个链表的长度。这种方法时间复杂度过高,不予考虑。

    方法二,将两个链表顺序遍历后依次将结点放入两个栈中,然后开始弹出结点,比较栈顶元素是否相同,如果相同,则比较下一个栈顶,直到找到最后一个相同的结点,则找到了第一个公共结点。时间复杂度为O(m+n)。但是这里使用了两个栈,相当于是空间消耗换取了时间效率。我们还有更好的方法,不需要辅助的栈。

    方法三,先遍历两个链表,得到两个链表的长度,得到两个链表哪个长,长链表比短链表长几个结点。然后进行第二次遍历,在较长的链表上先走若干步使两个链表最后能同时到达尾结点,接着在同时在两个链表上遍历,找到的第一个相同的结点就是他们的第一个公共结点。时间复杂度为O(m+n)。实现如下:

ListNode* 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!=pListHeadShort))
    {
        pListHeadLong=pListHeadLong->m_pNext;
        pListHeadShort=pListHeadShort->m_pNext;
    }
    
    ListNode* pFirstCommonNode=pListHeadLong;
    
    return pFirstCommonNode;
}

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


本文出自 “仙路千叠惊尘梦” 博客,请务必保留此出处http://secondscript.blog.51cto.com/9370042/1586719

两个链表的第一个公共结点