| 题目：输入两个链表，找出它们的第一个公共结点。 |
链表结点定义如下：
struct ListNode { int m_nKey; ListNode *m_pNext; };
解决办法：首先遍历两个链表得到它们的长度，就能知道哪个链表比较长，以及长的链表比短的链表多几个结点。在第二次遍历的时候，在较长的链表上先走若干步，接着再同时在两个链表上遍历，找到的第一个相同的结点就是它们的第一个公共结点。
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;
}
微信公众号： 猿人谷
如果您认为阅读这篇博客让您有些收获，不妨点击一下右下角的【推荐】
如果您希望与我交流互动，欢迎关注微信公众号
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接。
