mysileng

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

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

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

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

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

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

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

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

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

//@heyaming, 第一節,求鏈表倒數第k個結點應該考慮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;
} 

 

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

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

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

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

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

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

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

 

1. //copyright@ KurtWang  
2. //July、2011.05.27。  
3. struct Node  
4. {  
5.     int value;  
6.     Node * next;  
7. };  
8.   
9. //1.先判斷帶不帶環  
10. //判斷是否有環，返回bool，如果有環，返回環里的節點  
11. //思路：用兩個指針，一個指針步長為1，一個指針步長為2，判斷鏈表是否有環  
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、如果都不帶環，就判斷尾節點是否相等，如果都帶環，判斷一鏈表上倆指針相遇的那個節點，在不在另一條鏈表上。下面是綜合解決這個問題的代碼：

 

1. //判斷帶環不帶環時鏈表是否相交  
2. //2.如果都不帶環，就判斷尾節點是否相等  
3. //3.如果都帶環，判斷一鏈表上倆指針相遇的那個節點，在不在另一條鏈表上。  
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.     //一個有環，一個無環  
15.     if(isCircle1 != isCircle2)  
16.         return false;  
17.     //兩個都無環，判斷最后一個節點是否相等  
18.     else if(!isCircle1 && !isCircle2)  
19.     {  
20.         return lastNode1 == lastNode2;  
21.     }  
22.     //兩個都有環，判斷環里的節點是否能到達另一個鏈表環里的節點  
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：求兩個鏈表相交的第一個節點
思路：在判斷是否相交的過程中要分別遍歷兩個鏈表，同時記錄下各自長度。

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

    代碼如下：

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

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

分析：我盡量以最清晰的方式來說明這個問題（大部分內容來自ivan，big等人的討論）：
      1、首先題目要求很簡單，就是要你想辦法讓A最終能趕上B，A在后，B在前，都向右移動，如果它們的速度永遠一致，那A是永遠無法追趕上B的。但題目給出了一個條件判斷指令，即如果A或B某個機器人向前移動時，若是某個機器人經過的點是第二個機器人曾經經過的點，那么程序返回true。對的，就是抓住這一點，A到達曾經B經過的點后，發現此后的路是B此前經過的，那么A開始提速兩倍，B一直保持原來的一倍速度不變，那樣的話，A勢必會在|AB|/move_right個單位時間內，追上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到達B點前，兩者都只有第一條if為真，即以相同的速度向右移動，在A到達B后，A只滿足第二個if，即以兩倍的速度向右移動，B依然只滿足第一個if，則速度保持不變，經過|AB|/move_right個單位時間，A就可以追上B。

     2、有個細節又出現了，正如ivan所說，

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

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

那作如何修改呢?:

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的速度應該比B快了。

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

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

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

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