229
Cracking the Coding Interview:: 尋找有環鏈表的環路起始節點
給定一個有環鏈表，實現一個算法返回環路的開頭節點。 這個問題是由經典麵試題-檢測鏈表是否存在環路演變而來。這個問題也是編程之美的判斷兩個鏈表是否相交的擴展問題。
首先回顧一下編程之美的問題。 由於如果兩個鏈表如果相交，那麼交點之後node都是共享（地址相同）的，因此最簡單暴力的方法就是兩個for循環，判斷該鏈表的node是否屬於另外一個鏈表。但是這個算法複雜度是O(length1 * length2)。如果鏈表較長，這個複雜度有點高了。
當然也可以遍曆其中某個鏈表，將node的地址存儲hash table中；然後接下來遍曆另外一個鏈表，查找node是否在這個hash table中。這樣的話時間複雜度就是O(length1 + length2)。但是需要額外的O(length1)的空間。在C++ STL Java等主流語言中，hash table都有很好的實現，因此編程也比較簡單。
注意我們這個方法是認定如果兩個鏈表相交，那麼肯定交點以後的點都是共享的，包括最後一個點。那麼找到鏈表的最後一個節點，如果節點相同，那麼就相交。當然了，以上算法需要處理有環存在的情況。
本文的問題是尋找有環鏈表的開頭節點，那麼如何判斷一個鏈表是否有環？
我們可以用快慢遊標的方法。具體來說，就是使用兩個遊標遍曆鏈表，其中快遊標（快指針，fastRunner）每次經過兩個node，慢遊標（慢指針，slowRunner）每次經過一個node。那麼如果有環，那麼這兩個遊標肯定會相遇。使用反證法可以推理這個推論是正確的，假如fastRunner正好經過了slowRunner，而沒有相遇，那麼上一部，就是fastRunner後退兩步，slowRunner後退一步，兩個runner必定相遇。如果現在slowRunner正好領先一步fastRunner，那麼下一步二者相遇。
bool checkLinkRing(const Node *head)
{
if( head == nullptr )
return false;
auto fastRunner = head;
auto slowRunner = head;
while( fastRunner->next != nullptr && fastRunner->next->next != nullptr )
{
fastRunner = fastRunner->next->next;
slowRunner = slowRunner->next;
if( fastRunner == slowRunner )
return true;
}
return false;
}
接下來的問題，如何找到環的起始點？看下圖，假設交點在K處
那麼在slowRunner走了K步到達交點，那麼此時fastRunner走了2K步到達黃圈處。那麼fastRunner距離追上slowRunner還有RingSize - K步。 注意，隻能順時針前進。fastRunner相對slowRunner的速度是每步經過一個node（fastRunner雖然每次經過2個node，但是slowRunner也向前走了一個node，因此每步二者的距離僅僅減少一個node），因此在走了RingSize - K時相遇。也就是slowRunner在進入環後，再走RingSize - K 步後二者相遇於綠處。此時，綠點順時針距離交點有RingSize - ( RingSize - K) = K。注意括號內的RingSize - K是slowRunner走的。
關鍵問題出來了，在二者相遇的點，距離交點也是K： 與head到交點的距離相同。因此，我們可以調整兩個遊標，使slowRunnder從頭開始，fastRunnder從相遇點開始，二者以相同的速度前行，必然在相交點再次相遇！
auto findRingCrossPoint(const Node *head) ->decltype(head)
{
if( head == nullptr )
return nullptr;
auto fastRunner = head;// C++11, fastRunner is const Node *
auto slowRunner = head;
while( fastRunner->next != nullptr && fastRunner->next->next != nullptr )
{
fastRunner = fastRunner->next->next;
slowRunner = slowRunner->next;
if( fastRunner == slowRunner )
break;
}
// in case that there is no ring.
if( fastRunner != slowRunner )
return nullptr;
slowRunner = head;
while( true )
{
fastRunner = fastRunner->next;
slowRunner = slowRunner->next;
if( fastRunner == slowRunner )
{
break;
}
}
return fastRunner;
}
最後更新：2017-04-03 12:53:57