mysileng

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

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

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

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

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

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

    那在平時(shí)準(zhǔn)備面試的過(guò)程中如何加強(qiáng)這一方面的意識(shí)呢?我想，除了平時(shí)遇到一道面試題，盡可能用多種思路解決，以延伸自己的視野之外，便是平時(shí)有意注意觀(guān)察生活。因?yàn)椋嘈牛愫苋菀琢私獾剑鋵?shí)這種鏈表追趕的問(wèn)題來(lái)源于生活中長(zhǎng)跑比賽，如果平時(shí)注意多多思考，多多積累，多多發(fā)現(xiàn)并體味生活，相信也會(huì)對(duì)面試有所幫助。

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

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

//@heyaming, 第一節(jié),求鏈表倒數(shù)第k個(gè)結(jié)點(diǎn)應(yīng)該考慮k大于鏈表長(zhǎng)度的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;
} 

 

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

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

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

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

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

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

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

 

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é)點(diǎn)  
11. //思路：用兩個(gè)指針，一個(gè)指針步長(zhǎng)為1，一個(gè)指針步長(zhǎng)為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é)點(diǎn)是否相等，如果都帶環(huán)，判斷一鏈表上倆指針相遇的那個(gè)節(jié)點(diǎn)，在不在另一條鏈表上。下面是綜合解決這個(gè)問(wèn)題的代碼：

 

1. //判斷帶環(huán)不帶環(huán)時(shí)鏈表是否相交  
2. //2.如果都不帶環(huán)，就判斷尾節(jié)點(diǎn)是否相等  
3. //3.如果都帶環(huán)，判斷一鏈表上倆指針相遇的那個(gè)節(jié)點(diǎn)，在不在另一條鏈表上。  
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.     //一個(gè)有環(huán)，一個(gè)無(wú)環(huán)  
15.     if(isCircle1 != isCircle2)  
16.         return false;  
17.     //兩個(gè)都無(wú)環(huán)，判斷最后一個(gè)節(jié)點(diǎn)是否相等  
18.     else if(!isCircle1 && !isCircle2)  
19.     {  
20.         return lastNode1 == lastNode2;  
21.     }  
22.     //兩個(gè)都有環(huán)，判斷環(huán)里的節(jié)點(diǎn)是否能到達(dá)另一個(gè)鏈表環(huán)里的節(jié)點(diǎn)  
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. }  

 

擴(kuò)展2：求兩個(gè)鏈表相交的第一個(gè)節(jié)點(diǎn)
思路：在判斷是否相交的過(guò)程中要分別遍歷兩個(gè)鏈表，同時(shí)記錄下各自長(zhǎng)度。

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

    代碼如下：

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

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

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

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

再簡(jiǎn)單解釋下上面的偽代碼（@big）：
A------------B
|                  |
在A到達(dá)B點(diǎn)前，兩者都只有第一條if為真，即以相同的速度向右移動(dòng)，在A到達(dá)B后，A只滿(mǎn)足第二個(gè)if，即以?xún)杀兜乃俣认蛴乙苿?dòng)，B依然只滿(mǎn)足第一個(gè)if，則速度保持不變，經(jīng)過(guò)|AB|/move_right個(gè)單位時(shí)間，A就可以追上B。

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

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

上面這個(gè)分支不一定能提速的。why?因?yàn)槿绻鹖f條件花的時(shí)間很少，而move指令發(fā)的時(shí)間很大（實(shí)際很可能是這樣），那么兩個(gè)機(jī)器人的速度還是基本是一樣的。

那作如何修改呢?:

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、然要是說(shuō)每個(gè)指令處理速度都很快，AB豈不是一直以相同的速度右移了?那到底該作何修改呢?請(qǐng)看：

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

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

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