面试题37:两个链表的第一个公共节点

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

ListNode
1
2
3
4
{
int value;
ListNode* next;
}


分析

解法有两种,分别介绍如下:

第一种,先分别在两个链表上遍历一次,统计出两个链表的长度,假设为length1和length2,且length1>length2。然后在较长的链表上先走(length1-length2)步,然后两个同时走,如果遇到相等的,就表示找到了。

代码如下:

FindFirstCommenNode(ListNode* head1,ListNode* head2)
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
{
if(head1==NULL || head2==NULL)
return NULL;
int count1=0,count2=0;
int i;
ListNode* cur1=head1,*cur2=head2;
while(cur1!=NULL)
{
count1++;
cur1=cur1->next;
}
while(cur2!=NULL)
{
count2++;
cur2=cur2->next;
}
cur1=head1,cur2=head2;
if(count1>count2)
{
for(i=0;i<count1-count2;++i)
{
cur1=cur1->next;
}
}
else if(count2>count1)
{
for(i=0;i<count2-count1;++i)
{
cur2=cur2->next;
}
}
while(cur1!=NULL && cur2!=NULL)
{
if(cur1==cur2)
{
return cur1;
}
else
{
cur1=cur1->next;
cur2=cur2->next;
}
}
}

以上这种方法会将两个链表都遍历两次,有没有办法治遍历一次呢?答案是有的。我们只需要将每个节点的指针都各自放进一个栈中,然后从栈中逐个弹出。若某一次弹出的两个节点不相等,则上一次弹出的就是他们的第一个公共节点。

代码如下:

FindFirstCommenNode(ListNode* head1,ListNode* head2)
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
53
54
55
56
57
58
{
if(head1==NULL || head2==NULL)
return NULL;
stack<ListNode*> s1,s2;
ListNode* cur1=head1,*cur2=head2;
while(cur1!=NULL || cur2!=NULL)
{
if(cur1!=NULL)
{
s1.push(cur1);
cur1=cur1->next;
}
if(cur2!=NULL)
{
s2.push(cur2);
cur2=cur2->next;
}
}
while(!s1.empty() || !s2.empty())
{
if(!s1.empty() && !s2.empty())
{
if(s1.top()==s2.top())
{
s1.pop();
s2.pop();
}
else
{
return s1.top()->next;
}
}
else if(!s1.empty())
{
if(s1.top()->next==head2)
{
return head2;
}
else
{
return NULL;
}
}
else if(!s2.empty())
{
if(s2.top()->next==head1)
{
return head1;
}
else
{
return NULL;
}
}
}
if(s1.empty() && s2.empty())
return head1;
}

以上

如果你有任何想法或是可以改进的地方,欢迎和我交流!

完整代码及测试用例在github上:点我前往

<div>来自为知笔记(Wiz)</div>