面试题解(1):单向链表相关-白红宇

从网上收集来的一些面试题和解题思路，加以整理，供参考。

问题0. 一个单向链表，请设计算法判断该链表中有没有环？

思路1：

声明一个指向链首的指针和一个足够大的int数组(或hash表，用于保存地址)，逐个节点地遍历链表；遍历过程中，先判断该节点的地址是否已经在数组中存在了，如果不存在，则将该地址加入数组并让指针指向下一个节点；如果存在，则证明链表中有环。这种方法需要用数组来保存地址，并反复遍历该数组，效率很低，伪代码如下：

Node

ptr

head;

链首

int

100000

];

int

len

;

while

(ptr

null

)

{

int address = ptr;

if(address already in i)

{

print '链表中存在环';

exit();

}

i[len] = ptr;

ptr = ptr->next;

}

链表中没有环

exit();

思路2：

如果链表中有环的话，则整个链表呈6、9、或0字形；可以声明两个指向链首的指针，其中一个指针每次移动一个节点，另一个指针每次移动两个节点，如果两个指针指向同一个节点，则表示链表中存在环(类似与小学数学中的

追击问题

=_=)，否则不存在环。伪代码如下：

Node

ptr1

head;

Node

ptr2

head;

(ptr1

null

)

ptr1

next;

(ptr1

ptr2)

考虑链表中只有一个元素，且构成一个环的情况

{

print '链表中存在环';

exit();

}

ptr2

next;

或者ptr1->next;

while

(

true

)

{

if(ptr1==null || ptr2==null)

{

print '链表中没有环';

break;

}

if(ptr1==ptr2)

{

print '链表中存在环';

break;

}

ptr1 = ptr1->next;

if(ptr2->next != null)

ptr2 = ptr2->next->next;

}

exit();

问题1. 两个单向链表，有可能交叉，请设计算法判断是否交叉，如果交叉，返回交叉点！

思路：

两个单向链表交叉，则呈“Y”字型(存在环的话比较复杂，这里暂不考虑的存在环的情况)，且链首在“Y”字形的上面分叉部分。于是可以先找到p1，p2的最后一个节点(各自遍历)，同时记录节点数量a，b；然后判断最后一个节点是否相同，如果不相同则没相交；如果相同，则从一个节点和|a-b|+1个节点开始比较看是否相等，不相等都寻找下一个节点直到找到交叉点。伪代码如下：

int

count1

;

int

count2

;

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++;

}

(tail1

tail2)

{

print '两个链表没有交叉';

exit();

}

ptr1

count1

count2

head2 : head1;

ptr2

count1

count2

head1 : head2;

int

count

;

int

len

count1

count2

;

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，如需转载请自行联系原作者