前奏
有這樣一個問題：在一條左右水平放置的直線軌道上任選兩個點，放置兩個機器人，請用如下指令系統為機器人設計控制程序，使這兩個機器人能夠在直線軌道上相遇。（注意兩個機器人用你寫的同一個程序來控制）。
指令系統：只包含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，判斷這兩個鏈表是否相交。這裡為了簡化問題，我們假設兩個鏈表均不帶環。
分析：這是來自編程之美上的微軟亞院的一道面試題目。請跟著我的思路步步深入（部分文字引自編程之美）：
直接循環判斷第一個鏈表的每個節點是否在第二個鏈表中。但，這種方法的時間復雜度為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.如果都帶環，判斷一鏈表上倆指針相遇的那個節點，在不在另一條鏈表上。
如果在，則相交，如果不在，則不相交。
1、那麼，如何編寫代碼來判斷鏈表是否有環呢?因為很多的時候，你給出了問題的思路後，面試官可能還要追加你的代碼，ok，如下（設置兩個指針(p1, p2)，初始值都指向頭，p1每次前進一步，p2每次前進二步，如果鏈表存在環，則p2先進入環，p1後進入環，兩個指針在環中走動，必定相遇）：
view plaincopy to clipboardprint?
//copyright@ KurtWang
//July、2011.05.27。
struct Node
{
int value;
Node * next;
};
//1.先判斷帶不帶環
//判斷是否有環，返回bool，如果有環，返回環裡的節點
//思路：用兩個指針，一個指針步長為1，一個指針步長為2，判斷鏈表是否有環
bool isCircle(Node * head, Node *& circleNode, Node *& lastNode)
{
Node * fast = head->next;
Node * slow = head;
while(fast != slow && fast && slow)
{
if(fast->next != NULL)
fast = fast->next;
if(fast->next == NULL)
lastNode = fast;
if(slow->next == NULL)
lastNode = slow;
fast = fast->next;
slow = slow->next;
}
if(fast == slow && fast && slow)
{
circleNode = fast;
return true;
}
else
return false;
}
//copyright@ KurtWang
//July、2011.05.27。
struct Node
{
int value;
Node * next;
};
//1.先判斷帶不帶環
//判斷是否有環，返回bool，如果有環，返回環裡的節點
//思路：用兩個指針，一個指針步長為1，一個指針步長為2，判斷鏈表是否有環
bool isCircle(Node * head, Node *& circleNode, Node *& lastNode)
{
Node * fast = head->next;
Node * slow = head;
while(fast != slow && fast && slow)
{
if(fast->next != NULL)
fast = fast->next;
if(fast->next == NULL)
lastNode = fast;
if(slow->next == NULL)
lastNode = slow;
fast = fast->next;
slow = slow->next;
}
if(fast == slow && fast &
