题目描述
输入两个链表，找出它们的第一个公共结点
原理
因为拥有一个共同节点，所以先遍历两个链表得到他们的长度，就能知道哪个链表比较长，以及长的链表比短的链表多几个结点(diff，如果一样长则diff为0)。在第二次遍历的时候，在较长的链表上先走若干(diff)步，接着同时在两个链表上遍历，找到的第一个相同的结点就是他们的第一个公共结点
代码实现
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
47
48
49
50
51
52
| struct ListNode
{
int val;
struct ListNode* next;
ListNode(int x, ListNode* ptr = nullptr) :
val(x), next(ptr) {}
};
ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2)
{
int count1 = 0;
int count2 = 0;
ListNode* nHead1 = pHead1;
ListNode* nHead2 = pHead2;
ListNode* res = nullptr;
while (pHead1 != nullptr)
{
count1++;
pHead1 = pHead1->next;
}
while (pHead2 != nullptr)
{
count2++;
pHead2 = pHead2->next;
}
int diff = count1 - count2;
if (diff > 0)
{
for (int i = 0; i < diff; i++)
nHead1 = nHead1->next;
} else
{
diff *= -1;
for (auto i = 0; i < diff; i++)
nHead2 = nHead2->next;
}
while (nHead1 != nullptr && nHead2 != nullptr)
{
if (nHead1 != nHead2)
{
nHead1 = nHead1->next;
nHead2 = nHead2->next;
}
else
{
res = nHead1;
return res;
}
}
return res;
}
|
输入为
1
| [1,2,3,4,5,9,10],[12,11,9,10]
|
输出为
