首页 > 代码库 > 两个链表的第一个公共结点
两个链表的第一个公共结点
题目:输入两个链表,找出他们的第一个公共结点。链表定义如下:
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
两个链表的第一个公共结点
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。