作者：July、狂想曲創作組。
前奏
有這樣一個問題：在一條左右水平放置的直線軌道上任選兩個點，放置兩個機器人，請用如下指令系統為機器人設計控制程序，使這兩個機器人能夠在直線軌道上相遇。（注意兩個機器人用你寫的同一個程序來控制）。
指令系統：只包含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;
ListNode* fun(ListNode *head,int k)
{
pone = ptwo = head;
for(int i=0;i<=k-1;i++)
ptwo=ptwo->next;
while(ptwo!=NULL)
{
pone=pone->next;
ptwo=ptwo->next;
}
return pone;
}
擴展：
這是針對鏈表單項鏈表查找其中倒數第k個結點。試問，如果鏈表是雙向的，且可能存在環呢?請看第二節、編程判斷兩個鏈表是否相交。
第二節、編程判斷兩個鏈表是否相交
題目描述：給出兩個單向鏈表的頭指針（如下圖所示），
比如h1、h2，判斷這兩個鏈表是否相交。這裡為了簡化問題，我們假設兩個鏈表均不帶環。
分析：這是來自編程之美上的微軟亞院的一道面試題目。請跟著我的思路步步深入（部分文字引自編程之美）：
直接循環判斷第一個鏈表的每個節點是否在第二個鏈表中。但，這種方法的時間復雜度為O(Length(h1) * Length(h2))。顯然，我們得找到一種更為有效的方法，至少不能是O（N^2）的復雜度。
針對第一個鏈表直接構造hash表，然後查詢hash表，判斷第二個鏈表的每個結點是否在hash表出現，如果所有的第二個鏈表的結點都能在hash表中找到，即說明第二個鏈表與第一個鏈表有相同的結點。時間復雜度為為線性：O(Length(h1) + Length(h2))，同時為了存儲第一個鏈表的所有節點，空間復雜度為O(Length(h1))。是否還有更好的方法呢，既能夠以線性時間復雜度解決問題，又能減少存儲空間？
進一步考慮“如果兩個沒有環的鏈表相交於某一節點，那麼在這個節點之後的所有節點都是兩個鏈表共有的”這個特點，我們可以知道，如果它們相交，則最後一個節點一定是共有的。而我們很容易能得到鏈表的最後一個節點，所以這成了我們簡化解法的一個主要突破口。那麼，我們只要判斷倆個鏈表的尾指針是否相等。相等，則鏈表相交；否則，鏈表不相交。
所以，先遍歷第一個鏈表，記住最後一個節點。然後遍歷第二個鏈表，到最後一個節點時和第一個鏈表的最後一個節點做比較，如果相同，則相交，否則，不相交。這樣我們就得到了一個時間復雜度，它為O((Length(h1) + Length(h2))，而且只用了一個額外的指針來存儲最後一個節點。這個方法時間復雜度為線性O（N），空間復雜度為O（1），顯然比解法三更勝一籌。
上面的問題都是針對鏈表無環的，那麼如果現在，鏈表是有環的呢?還能找到最後一個結點進行判斷麼?上面的方法還同樣有效麼?顯然，這個問題的本質已經轉化為判斷鏈表是否有環。那麼，如何來判斷鏈表是否有環呢?
總結：
所以，事實上，這個判斷兩個鏈表是否相交的問題就轉化成了：
1.先判斷帶不帶環
2.如果都不帶環，就判斷尾節點是否相等
3.如果都帶環，判斷一鏈表上倆指針相遇的那個節點，在不在另一條鏈表上。
如果在，則相交，如果不在，則不相交。
那麼，如何編寫代碼來判斷鏈表是否有環呢?因為很多的時候，你給出了問題的思路後，面試官可能還要追加你的代碼，ok，如下：
//用兩個指針，一個指針步長為1，一個指針步長為2，判斷鏈表是否有環
bool check(const node* head)
{
if(head==NULL)
return false;
node *low=head, *fast=head->next;
while(fast!=NULL && fast->next!=NULL)
{
low=low->next;
fast=fast->next->next;
if(low==fast) return true;
}
return false;
}
問題又來了，如果鏈表可能有環，則如何判斷兩個鏈表是否相交，解決方案如下：
//思路：鏈表1 步長為1，鏈表2步長為2 ，如果有環且相交則肯定相遇，否則不相交
list1 head: p1
list2 head: p2
while( p1 != p2 && p1 != NULL && p2 != NULL )
//但當鏈表有環但不相交時，此處是死循環。!
{
p1 = p1->next;
if ( p2->next )
p2 = p2->next->next;
else
p2 = p2->next;
}
if ( p1 == p2 && p1 && p2)
//相交
else
//不相交
所以，判斷帶環的鏈表，相不相交，只能這樣：
如果都帶環，判斷一鏈表上倆指針相遇的那個節點，在不在另一條鏈表上。如果在，則相交，如果不在，則不相交。
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
上面這個分支不一定能提
