mysileng

作者：July、狂想曲創(chuàng)作組。
出處：http://blog.csdn.net/v_JULY_v 。

前奏
    有這樣一個問題：在一條左右水平放置的直線軌道上任選兩個點，放置兩個機器人，請用如下指令系統(tǒng)為機器人設(shè)計控制程序，使這兩個機器人能夠在直線軌道上相遇。（注意兩個機器人用你寫的同一個程序來控制）。
    指令系統(tǒng)：只包含4條指令，向左、向右、條件判定、無條件跳轉(zhuǎn)。其中向左（右）指令每次能控制機器人向左（右）移動一步；條件判定指令能對機器人所在的位置進(jìn)行條件測試，測試結(jié)果是如果對方機器人曾經(jīng)到過這里就返回true，否則返回false；無條件跳轉(zhuǎn)，類似匯編里面的跳轉(zhuǎn)，可以跳轉(zhuǎn)到任何地方。

    ok，這道很有意思的趣味題是去年微軟工程院的題，文末將給出解答（如果急切想知道此問題的答案，可以直接跳到本文第三節(jié)）。同時，我們看到其實這個題是一個典型的追趕問題，那么追趕問題在哪種面試題中比較常見?對了，鏈表追趕。本章就來闡述這個問題。有不正之處，望不吝指正。

第一節(jié)、求鏈表倒數(shù)第k個結(jié)點
第13題、題目描述：
輸入一個單向鏈表，輸出該鏈表中倒數(shù)第k個結(jié)點,
鏈表的倒數(shù)第0個結(jié)點為鏈表的尾指針。

分析：此題一出，相信，稍微有點 經(jīng)驗的同志，都會說到：設(shè)置兩個指針p1,p2，首先p1和p2都指向head，然后p2向前走k步，這樣p1和p2之間就間隔k個節(jié)點，最后p1和p2同時向前移動，直至p2走到鏈表末尾。

    前幾日有朋友提醒我說，讓我講一下此種求鏈表倒數(shù)第k個結(jié)點的問題。我想，這種問題，有點經(jīng)驗的人恐怕都已了解過，無非是利用兩個指針一前一后逐步前移。但他提醒我說，如果參加面試的人沒有這個意識，它怎么也想不到那里去。

    那在平時準(zhǔn)備面試的過程中如何加強這一方面的意識呢?我想，除了平時遇到一道面試題，盡可能用多種思路解決，以延伸自己的視野之外，便是平時有意注意觀察生活。因為，相信，你很容易了解到，其實這種鏈表追趕的問題來源于生活中長跑比賽，如果平時注意多多思考，多多積累，多多發(fā)現(xiàn)并體味生活，相信也會對面試有所幫助。

    ok，扯多了，下面給出這個題目的主體代碼，如下：

struct ListNode
{
    char data;
    ListNode* next;
};
ListNode* head,*p,*q;
ListNode *pone,*ptwo;

//@heyaming, 第一節(jié),求鏈表倒數(shù)第k個結(jié)點應(yīng)該考慮k大于鏈表長度的case。
ListNode* fun(ListNode *head,int k)
{
 assert(k >= 0);
 pone = ptwo = head;
 for( ; k > 0 && ptwo != NULL; k--)
  ptwo=ptwo->next;
 if (k > 0) return NULL;
 
 while(ptwo!=NULL)
 {
  pone=pone->next;
  ptwo=ptwo->next;
 }
 return pone;
} 

 

擴展：
這是針對鏈表單項鏈表查找其中倒數(shù)第k個結(jié)點。試問，如果鏈表是雙向的，且可能存在環(huán)呢?請看第二節(jié)、編程判斷兩個鏈表是否相交。

第二節(jié)、編程判斷兩個鏈表是否相交
題目描述：給出兩個單向鏈表的頭指針（如下圖所示）

比如h1、h2，判斷這兩個鏈表是否相交。這里為了簡化問題，我們假設(shè)兩個鏈表均不帶環(huán)。

分析：這是來自編程之美上的微軟亞院的一道面試題目。請跟著我的思路步步深入（部分文字引自編程之美）：

1. 直接循環(huán)判斷第一個鏈表的每個節(jié)點是否在第二個鏈表中。但，這種方法的時間復(fù)雜度為O(Length(h1) * Length(h2))。顯然，我們得找到一種更為有效的方法，至少不能是O（N^2）的復(fù)雜度。
2. 針對第一個鏈表直接構(gòu)造hash表，然后查詢hash表，判斷第二個鏈表的每個結(jié)點是否在hash表出現(xiàn)，如果所有的第二個鏈表的結(jié)點都能在hash表中找到，即說明第二個鏈表與第一個鏈表有相同的結(jié)點。時間復(fù)雜度為為線性：O(Length(h1) + Length(h2))，同時為了存儲第一個鏈表的所有節(jié)點，空間復(fù)雜度為O(Length(h1))。是否還有更好的方法呢，既能夠以線性時間復(fù)雜度解決問題，又能減少存儲空間？
3. 進(jìn)一步考慮“如果兩個沒有環(huán)的鏈表相交于某一節(jié)點，那么在這個節(jié)點之后的所有節(jié)點都是兩個鏈表共有的”這個特點，我們可以知道，如果它們相交，則最后一個節(jié)點一定是共有的。而我們很容易能得到鏈表的最后一個節(jié)點，所以這成了我們簡化解法的一個主要突破口。那么，我們只要判斷倆個鏈表的尾指針是否相等。相等，則鏈表相交；否則，鏈表不相交。
   所以，先遍歷第一個鏈表，記住最后一個節(jié)點。然后遍歷第二個鏈表，到最后一個節(jié)點時和第一個鏈表的最后一個節(jié)點做比較，如果相同，則相交，否則，不相交。這樣我們就得到了一個時間復(fù)雜度，它為O((Length(h1) + Length(h2))，而且只用了一個額外的指針來存儲最后一個節(jié)點。這個方法時間復(fù)雜度為線性O(shè)（N），空間復(fù)雜度為O（1），顯然比解法三更勝一籌。
4. 上面的問題都是針對鏈表無環(huán)的，那么如果現(xiàn)在，鏈表是有環(huán)的呢?還能找到最后一個結(jié)點進(jìn)行判斷么?上面的方法還同樣有效么?顯然，這個問題的本質(zhì)已經(jīng)轉(zhuǎn)化為判斷鏈表是否有環(huán)。那么，如何來判斷鏈表是否有環(huán)呢?

總結(jié)：
所以，事實上，這個判斷兩個鏈表是否相交的問題就轉(zhuǎn)化成了：
1.先判斷帶不帶環(huán)
2.如果都不帶環(huán)，就判斷尾節(jié)點是否相等
3.如果都帶環(huán)，判斷一鏈表上倆指針相遇的那個節(jié)點，在不在另一條鏈表上。
如果在，則相交，如果不在，則不相交。

    1、那么，如何編寫代碼來判斷鏈表是否有環(huán)呢?因為很多的時候，你給出了問題的思路后，面試官可能還要追加你的代碼，ok，如下（設(shè)置兩個指針(p1, p2)，初始值都指向頭，p1每次前進(jìn)一步，p2每次前進(jìn)二步，如果鏈表存在環(huán)，則p2先進(jìn)入環(huán)，p1后進(jìn)入環(huán)，兩個指針在環(huán)中走動，必定相遇）：

 

1. //copyright@ KurtWang  
2. //July、2011.05.27。  
3. struct Node  
4. {  
5.     int value;  
6.     Node * next;  
7. };  
8.   
9. //1.先判斷帶不帶環(huán)  
10. //判斷是否有環(huán)，返回bool，如果有環(huán)，返回環(huán)里的節(jié)點  
11. //思路：用兩個指針，一個指針步長為1，一個指針步長為2，判斷鏈表是否有環(huán)  
12. bool isCircle(Node * head, Node *& circleNode, Node *& lastNode)  
13. {  
14.     Node * fast = head->next;  
15.     Node * slow = head;  
16.     while(fast != slow && fast && slow)  
17.     {  
18.         if(fast->next != NULL)  
19.             fast = fast->next;  
20.           
21.         if(fast->next == NULL)  
22.             lastNode = fast;  
23.         if(slow->next == NULL)  
24.             lastNode = slow;  
25.           
26.         fast = fast->next;  
27.         slow = slow->next;  
28.           
29.     }  
30.     if(fast == slow && fast && slow)  
31.     {  
32.         circleNode = fast;  
33.         return true;  
34.     }  
35.     else  
36.         return false;  
37. }  

 

    2&3、如果都不帶環(huán)，就判斷尾節(jié)點是否相等，如果都帶環(huán)，判斷一鏈表上倆指針相遇的那個節(jié)點，在不在另一條鏈表上。下面是綜合解決這個問題的代碼：

 

1. //判斷帶環(huán)不帶環(huán)時鏈表是否相交  
2. //2.如果都不帶環(huán)，就判斷尾節(jié)點是否相等  
3. //3.如果都帶環(huán)，判斷一鏈表上倆指針相遇的那個節(jié)點，在不在另一條鏈表上。  
4. bool detect(Node * head1, Node * head2)  
5. {  
6.     Node * circleNode1;  
7.     Node * circleNode2;  
8.     Node * lastNode1;  
9.     Node * lastNode2;  
10.       
11.     bool isCircle1 = isCircle(head1,circleNode1, lastNode1);  
12.     bool isCircle2 = isCircle(head2,circleNode2, lastNode2);  
13.       
14.     //一個有環(huán)，一個無環(huán)  
15.     if(isCircle1 != isCircle2)  
16.         return false;  
17.     //兩個都無環(huán)，判斷最后一個節(jié)點是否相等  
18.     else if(!isCircle1 && !isCircle2)  
19.     {  
20.         return lastNode1 == lastNode2;  
21.     }  
22.     //兩個都有環(huán)，判斷環(huán)里的節(jié)點是否能到達(dá)另一個鏈表環(huán)里的節(jié)點  
23.     else  
24.     {  
25.         Node * temp = circleNode1->next;  //updated，多謝蒼狼 and hyy。  
26.         while(temp != circleNode1)    
27.         {  
28.             if(temp == circleNode2)  
29.                 return true;  
30.             temp = temp->next;  
31.         }  
32.         return false;  
33.     }  
34.       
35.     return false;  
36. }  

 

擴展2：求兩個鏈表相交的第一個節(jié)點
思路：在判斷是否相交的過程中要分別遍歷兩個鏈表，同時記錄下各自長度。

    @Joshua：這個算法需要處理一種特殊情況，即：其中一個鏈表的頭結(jié)點在另一個鏈表的環(huán)中，且不是環(huán)入口結(jié)點。這種情況有兩種意思：1)如果其中一個鏈表是循環(huán)鏈表，則另一個鏈表必為循環(huán)鏈表，即兩個鏈表重合但頭結(jié)點不同；2)如果其中一個鏈表存在環(huán)(除去循環(huán)鏈表這種情況)，則另一個鏈表必在此環(huán)中與此環(huán)重合，其頭結(jié)點為環(huán)中的一個結(jié)點，但不是入口結(jié)點。在這種情況下我們約定，如果鏈表B的頭結(jié)點在鏈表A的環(huán)中，且不是環(huán)入口結(jié)點，那么鏈表B的頭結(jié)點即作為A和B的第一個相交結(jié)點；如果A和B重合(定義方法時形參A在B之前)，則取B的頭結(jié)點作為A和B的第一個相交結(jié)點。 

    代碼如下：

    關(guān)于判斷單鏈表是否相交的問題，還可以看看此篇文章：http://www.shnenglu.com/humanchao/archive/2008/04/17/47357.html。ok，下面，回到本章前奏部分的那道非常有趣味的智力題。

第三節(jié)、微軟工程院面試智力題
題目描述：
    在一條左右水平放置的直線軌道上任選兩個點，放置兩個機器人，請用如下指令系統(tǒng)為機器人設(shè)計控制程序，使這兩個機器人能夠在直線軌道上相遇。（注意兩個機器人用你寫的同一個程序來控制）
    指令系統(tǒng)：只包含4條指令，向左、向右、條件判定、無條件跳轉(zhuǎn)。其中向左（右）指令每次能控制機器人向左（右）移動一步；條件判定指令能對機器人所在的位置進(jìn)行條件測試，測試結(jié)果是如果對方機器人曾經(jīng)到過這里就返回true，否則返回false；無條件跳轉(zhuǎn)，類似匯編里面的跳轉(zhuǎn)，可以跳轉(zhuǎn)到任何地方。

分析：我盡量以最清晰的方式來說明這個問題（大部分內(nèi)容來自ivan，big等人的討論）：
      1、首先題目要求很簡單，就是要你想辦法讓A最終能趕上B，A在后，B在前，都向右移動，如果它們的速度永遠(yuǎn)一致，那A是永遠(yuǎn)無法追趕上B的。但題目給出了一個條件判斷指令，即如果A或B某個機器人向前移動時，若是某個機器人經(jīng)過的點是第二個機器人曾經(jīng)經(jīng)過的點，那么程序返回true。對的，就是抓住這一點，A到達(dá)曾經(jīng)B經(jīng)過的點后，發(fā)現(xiàn)此后的路是B此前經(jīng)過的，那么A開始提速兩倍，B一直保持原來的一倍速度不變，那樣的話，A勢必會在|AB|/move_right個單位時間內(nèi)，追上B。ok，簡單偽代碼如下：

start:
if(at the position other robots have not reached)
    move_right
if(at the position other robots have reached)
    move_right
    move_right
goto start

再簡單解釋下上面的偽代碼（@big）：
A------------B
|                  |
在A到達(dá)B點前，兩者都只有第一條if為真，即以相同的速度向右移動，在A到達(dá)B后，A只滿足第二個if，即以兩倍的速度向右移動，B依然只滿足第一個if，則速度保持不變，經(jīng)過|AB|/move_right個單位時間，A就可以追上B。

     2、有個細(xì)節(jié)又出現(xiàn)了，正如ivan所說，

if(at the position other robots have reached)
    move_right
    move_right

上面這個分支不一定能提速的。why?因為如果if條件花的時間很少，而move指令發(fā)的時間很大（實際很可能是這樣），那么兩個機器人的速度還是基本是一樣的。

那作如何修改呢?:

start:
if(at the position other robots have not reached)
    move_right
    move_left
    move_right
if(at the position other robots have reached)
    move_right
goto start

-------

這樣改后，A的速度應(yīng)該比B快了。

      3、然要是說每個指令處理速度都很快，AB豈不是一直以相同的速度右移了?那到底該作何修改呢?請看：

go_step()
{
   向右
   向左
   向右
}
--------
三個時間單位才向右一步

go_2step()
{
   向右
}
------

    一個時間單向右一步向左和向右花的時間是同樣的，并且會占用一定時間。 如果條件判定指令時間比移令花的時間較少的話，應(yīng)該上面兩種步法，后者比前者快。至此，咱們的問題已經(jīng)得到解決。