| 题目：输入两个链表，找出它们的第一个公共结点。 |
链表结点定义如下：
struct ListNode
{
int m_nKey;
ListNode *m_pNext;
};
解决办法：首先遍历两个链表得到它们的长度，就能知道哪个链表比较长，以及长的链表比短的链表多几个结点。在第二次遍历的时候，在较长的链表上先走若干步，接着再同时在两个链表上遍历，找到的第一个相同的结点就是它们的第一个公共结点。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
ListNode
{
//得到两个链表的长度
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;
}
|