从网上收集来的一些面试题和解题思路，加以整理，供参考。
问题0. 一个单向链表，请设计算法判断该链表中有没有环？
思路1： 声明一个指向链首的指针和一个足够大的int数组(或hash表，用于保存地址)，逐个节点地遍历链表；遍历过程中，先判断该节点的地址是否已经在数组中存在了，如果不存在，则将该地址加入数组并让指针指向下一个节点；如果存在，则证明链表中有环。这种方法需要用数组来保存地址，并反复遍历该数组，效率很低，伪代码如下：
思路2： 如果链表中有环的话，则整个链表呈6、9、或0字形；可以声明两个指向链首的指针，其中一个指针每次移动一个节点，另一个指针每次移动两个节点，如果两个指针指向同一个节点，则表示链表中存在环(类似与小学数学中的 追击问题 =_=)，否则不存在环。伪代码如下：
问题1. 两个单向链表，有可能交叉，请设计算法判断是否交叉，如果交叉，返回交叉点！
思路： 两个单向链表交叉，则呈“Y”字型(存在环的话比较复杂，这里暂不考虑的存在环的情况)，且链首在“Y”字形的上面分叉部分。于是可以先找到p1，p2的最后一个节点(各自遍历)，同时记录节点数量a，b；然后判断最后一个节点是否相同，如果不相同则没相交；如果相同，则从一个节点和|a-b|+1个节点开始比较看是否相等，不相等都寻找下一个节点直到找到交叉点。伪代码如下：
int
count1
=
0
;
int
count2
=
0
;
Node
*
ptr1
=
head1;
Node
*
tail1
=
null
;
Node
*
ptr2
=
head2;
Node
*
tail2
=
null
;
while
(ptr1
!=
null
)
{
tail1 = ptr1;
ptr1 = ptr1 -> Next;
count1++;
}
while
(ptr2
!=
null
)
{
tail2 = ptr2;
ptr2 = ptr2 -> Next;
count1++;
}
if
(tail1
!=
tail2)
{
print '两个链表没有交叉';
exit();
}
ptr1
=
count1
>=
count2
?
head2 : head1;
ptr2
=
count1
>=
count2
?
head1 : head2;
int
count
=
0
;
int
len
=
|
count1
-
count2
|+
1
;
while
(ptr2
!=
null
)
{
count++;
if(count== len)
break;
ptr2 = ptr2->Next;
}
while
(ptr2
!=
null
)
{
if(ptr2 != ptr1)
{
ptr2 = ptr2->Next;
ptr1 = ptr1->Next;
}
else
{
print '交叉点';
exit();
}
}
问题0. 一个单向链表，请设计算法判断该链表中有没有环？
思路1： 声明一个指向链首的指针和一个足够大的int数组(或hash表，用于保存地址)，逐个节点地遍历链表；遍历过程中，先判断该节点的地址是否已经在数组中存在了，如果不存在，则将该地址加入数组并让指针指向下一个节点；如果存在，则证明链表中有环。这种方法需要用数组来保存地址，并反复遍历该数组，效率很低，伪代码如下：
1
Node
*
ptr
=
head;
//
链首
2
int
i[
100000
];
3
int
len
=
0
;
4
while
(ptr
!=
null
)
5
{
6 int address = ptr;
7 if(address already in i)
8 {
9 print '链表中存在环';
10 exit();
11 }
12 i[len] = ptr;
13 ptr = ptr->next;
14}
15print
'
链表中没有环
'
16exit();
Node
*
ptr
=
head;
//
链首
2
int
i[
100000
];3
int
len
=
0
;4
while
(ptr
!=
null
)5
{6
int address = ptr;7
if(address already in i)8
{9
print '链表中存在环';10
exit();11
}12
i[len] = ptr;13
ptr = ptr->next;14
}
15
print
'
链表中没有环
'
16
exit();
思路2： 如果链表中有环的话，则整个链表呈6、9、或0字形；可以声明两个指向链首的指针，其中一个指针每次移动一个节点，另一个指针每次移动两个节点，如果两个指针指向同一个节点，则表示链表中存在环(类似与小学数学中的 追击问题 =_=)，否则不存在环。伪代码如下：
1
Node
*
ptr1
=
head;
2Node
*
ptr2
=
head;
3
if
(ptr1
!=
null
)
4 ptr1
=
ptr1
->
next;
5
if
(ptr1
==
ptr2)
//
考虑链表中只有一个元素，且构成一个环的情况
6
{
7 print '链表中存在环';
8 exit();
9}
10ptr2
=
ptr2
->
next
->
next;
//
或者ptr1->next;
11
while
(
true
)
12
{
13 if(ptr1==null || ptr2==null)
14 {
15 print '链表中没有环';
16 break;
17 }
18 if(ptr1==ptr2)
19 {
20 print '链表中存在环';
21 break;
22 }
23 ptr1 = ptr1->next;
24 if(ptr2->next != null)
25 ptr2 = ptr2->next->next;
26}
27exit();
Node
*
ptr1
=
head;2
Node
*
ptr2
=
head;3
if
(ptr1
!=
null
)4
ptr1
=
ptr1
->
next;5
if
(ptr1
==
ptr2)
//
考虑链表中只有一个元素，且构成一个环的情况
6
{7
print '链表中存在环';8
exit();9
}
10
ptr2
=
ptr2
->
next
->
next;
//
或者ptr1->next;
11
while
(
true
)12
{13
if(ptr1==null || ptr2==null)14
{15
print '链表中没有环';16
break;17
}18
if(ptr1==ptr2)19
{20
print '链表中存在环';21
break;22
}23
ptr1 = ptr1->next;24
if(ptr2->next != null)25
ptr2 = ptr2->next->next;26
}
27
exit();
问题1. 两个单向链表，有可能交叉，请设计算法判断是否交叉，如果交叉，返回交叉点！
思路： 两个单向链表交叉，则呈“Y”字型(存在环的话比较复杂，这里暂不考虑的存在环的情况)，且链首在“Y”字形的上面分叉部分。于是可以先找到p1，p2的最后一个节点(各自遍历)，同时记录节点数量a，b；然后判断最后一个节点是否相同，如果不相同则没相交；如果相同，则从一个节点和|a-b|+1个节点开始比较看是否相等，不相等都寻找下一个节点直到找到交叉点。伪代码如下：
int
count1
=
0
;
int
count2
=
0
;Node
*
ptr1
=
head1;Node
*
tail1
=
null
;Node
*
ptr2
=
head2;Node
*
tail2
=
null
;
while
(ptr1
!=
null
)
{ tail1 = ptr1; ptr1 = ptr1 -> Next; count1++;}
while
(ptr2
!=
null
)
{ tail2 = ptr2; ptr2 = ptr2 -> Next; count1++;}
if
(tail1
!=
tail2)
{ print '两个链表没有交叉'; exit();}
ptr1
=
count1
>=
count2
?
head2 : head1;ptr2
=
count1
>=
count2
?
head1 : head2;
int
count
=
0
;
int
len
=
|
count1
-
count2
|+
1
;
while
(ptr2
!=
null
)
{ count++; if(count== len) break; ptr2 = ptr2->Next;}
while
(ptr2
!=
null
)
{ if(ptr2 != ptr1) { ptr2 = ptr2->Next; ptr1 = ptr1->Next; } else { print '交叉点'; exit(); } }
本文转自Silent Void博客园博客，原文链接：http://www.cnblogs.com/happyhippy/archive/2008/02/02/1062735.html，如需转载请自行联系原作者
