從網上收集來的一些面試題和解題思路，加以整理，供參考。
問題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
}
15
print '連結清單中沒有環'
16
exit();
思路2：如果連結清單中有環的話，則整個連結清單呈6、9、或0字形；可以聲明兩個指向鍊首的指針，其中一個指針每次移動一個節點，另一個指針每次移動兩個節點，如果兩個指針指向同一個節點，則表示連結清單中存在環(類似與國小數學中的追擊問題=_=)，否則不存在環。僞代碼如下：
Node * ptr1 = head;
Node * ptr2 = head;
if(ptr1 != null)
ptr1 = ptr1->next;
if(ptr1 == ptr2)//考慮連結清單中隻有一個元素，且構成一個環的情況
print '連結清單中存在環';
ptr2 = ptr2->next->next;//或者ptr1->next;
while(true)
if(ptr1==null || ptr2==null)
print '連結清單中沒有環';
break;
17
18
if(ptr1==ptr2)
19
20
21
22
23
24
if(ptr2->next != null)
25
ptr2 = ptr2->next->next;
26
27
問題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;
if(tail1 != tail2)
print '兩個連結清單沒有交叉';
ptr1 = count1>=count2 ? head2 : head1;
ptr2 = count1>=count2 ? head1 : head2;
int count = 0;
int len = |count1-count2|+1;
{
count++;
if(count== len)
ptr2 = ptr2->Next;
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，如需轉載請自行聯系原作者