原文：http://wuchong.me/blog/2014/03/25/interview-link-questions/

鏈表問題在面試過程中也是很重要也很基礎的一部分，鏈表本身很靈活，很考查編程功底，所以是很值得考的地方。我將復習過程中覺得比較好的鏈表問題整理了下。

下面是本文所要用到鏈表節(jié)點的定義：

1 2 3 4

struct Node{ int data; Node* next; };

?

1. 在O(1)時間刪除鏈表節(jié)點

題目描述：給定鏈表的頭指針和一個節(jié)點指針，在O(1)時間刪除該節(jié)點。[Google面試題]

分析：本題與《編程之美》上的「從無頭單鏈表中刪除節(jié)點」類似。主要思想都是「貍貓換太子」，即用下一個節(jié)點數(shù)據(jù)覆蓋要刪除的節(jié)點，然后刪除下一個節(jié)點。但是如果節(jié)點是尾節(jié)點時，該方法就行不通了。

代碼如下：

1 2 3 4 5 6 7 8 9 10

//O(1)時間刪除鏈表節(jié)點，從無頭單鏈表中刪除節(jié)點 void deleteRandomNode(Node *cur) { assert(cur != NULL); assert(cur->next != NULL); //不能是尾節(jié)點 Node* pNext = cur->next; cur->data = pNext->data; cur->next = pNext->next; delete pNext; }

?

2. 單鏈表的轉置

題目描述：輸入一個單向鏈表，輸出逆序反轉后的鏈表

分析：鏈表的轉置是一個很常見、很基礎的數(shù)據(jù)結構題了，非遞歸的算法很簡單，用三個臨時指針 pre、head、next 在鏈表上循環(huán)一遍即可。遞歸算法也是比較簡單的，但是如果思路不清晰估計一時半會兒也寫不出來吧。

下面是循環(huán)版本和遞歸版本的鏈表轉置代碼：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

//單鏈表的轉置,循環(huán)方法 Node* reverseByLoop(Node *head) { if(head == NULL || head->next == NULL) return head; Node *pre = NULL; Node *next = NULL; while(head != NULL) { next = head->next; head->next = pre; pre = head; head = next; } return pre; } //單鏈表的轉置,遞歸方法 Node* reverseByRecursion(Node *head) { //第一個條件是判斷異常，第二個條件是結束判斷 if(head == NULL || head->next == NULL) return head; Node *newHead = reverseByRecursion(head->next); head->next->next = head; head->next = NULL; return newHead; //返回新鏈表的頭指針 }

?

3. 求鏈表倒數(shù)第k個節(jié)點

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

分析：設置兩個指針 p1、p2，首先 p1 和 p2 都指向 head，然后 p2 向前走 k 步，這樣 p1 和 p2 之間就間隔 k 個節(jié)點，最后 p1 和 p2 同時向前移動，直至 p2 走到鏈表末尾。

代碼如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

//倒數(shù)第k個節(jié)點 Node* theKthNode(Node *head,int k) { if(k < 0) return NULL; //異常判斷 Node *slow,*fast; slow = fast = head; int i = k; for(;i>0 && fast!=NULL;i--) { fast = fast->next; } if(i > 0) return NULL; //考慮k大于鏈表長度的case while(fast != NULL) { slow = slow->next; fast = fast->next; } return slow; }

?

4. 求鏈表的中間節(jié)點

題目描述：求鏈表的中間節(jié)點，如果鏈表的長度為偶數(shù)，返回中間兩個節(jié)點的任意一個，若為奇數(shù)，則返回中間節(jié)點。

分析：此題的解決思路和第3題「求鏈表的倒數(shù)第 k 個節(jié)點」很相似。可以先求鏈表的長度，然后計算出中間節(jié)點所在鏈表順序的位置。但是如果要求只能掃描一遍鏈表，如何解決呢？最高效的解法和第3題一樣，通過兩個指針來完成。用兩個指針從鏈表頭節(jié)點開始，一個指針每次向后移動兩步，一個每次移動一步，直到快指針移到到尾節(jié)點，那么慢指針即是所求。

代碼如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

//求鏈表的中間節(jié)點 Node* theMiddleNode(Node *head) { if(head == NULL) return NULL; Node *slow,*fast; slow = fast = head; //如果要求在鏈表長度為偶數(shù)的情況下，返回中間兩個節(jié)點的第一個，可以用下面的循環(huán)條件 //while(fast && fast->next != NULL && fast->next->next != NULL) while(fast != NULL && fast->next != NULL) { fast = fast->next->next; slow = slow->next; } return slow; }

?

5. 判斷單鏈表是否存在環(huán)

題目描述：輸入一個單向鏈表，判斷鏈表是否有環(huán)？

分析：通過兩個指針，分別從鏈表的頭節(jié)點出發(fā)，一個每次向后移動一步，另一個移動兩步，兩個指針移動速度不一樣，如果存在環(huán)，那么兩個指針一定會在環(huán)里相遇。

代碼如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

//判斷單鏈表是否存在環(huán),參數(shù)circleNode是環(huán)內(nèi)節(jié)點，后面的題目會用到 bool hasCircle(Node *head,Node *&circleNode) { Node *slow,*fast; slow = fast = head; while(fast != NULL && fast->next != NULL) { fast = fast->next->next; slow = slow->next; if(fast == slow) { circleNode = fast; return true; } } return false; }

?

6. 找到環(huán)的入口點

題目描述：輸入一個單向鏈表，判斷鏈表是否有環(huán)。如果鏈表存在環(huán)，如何找到環(huán)的入口點？

解題思路：?由上題可知，按照 p2 每次兩步，p1 每次一步的方式走，發(fā)現(xiàn) p2 和 p1 重合，確定了單向鏈表有環(huán)路了。接下來，讓p2回到鏈表的頭部，重新走，每次步長不是走2了，而是走1，那么當 p1 和 p2 再次相遇的時候，就是環(huán)路的入口了。

為什么？：假定起點到環(huán)入口點的距離為 a，p1 和 p2 的相交點M與環(huán)入口點的距離為b，環(huán)路的周長為L，當 p1 和 p2 第一次相遇的時候，假定 p1 走了 n 步。那么有：

p1走的路徑：?a+b ＝ n；
p2走的路徑：?a+b+k*L = 2*n； p2 比 p1 多走了k圈環(huán)路，總路程是p1的2倍

根據(jù)上述公式可以得到?k*L=a+b=n顯然，如果從相遇點M開始，p1 再走 n 步的話，還可以再回到相遇點，同時p2從頭開始走的話，經(jīng)過n步，也會達到相遇點M。

顯然在這個步驟當中 p1 和 p2 只有前 a 步走的路徑不同，所以當 p1 和 p2 再次重合的時候，必然是在鏈表的環(huán)路入口點上。

代碼如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

//找到環(huán)的入口點 Node* findLoopPort(Node *head) { //如果head為空，或者為單結點，則不存在環(huán) if(head == NULL || head->next == NULL) return NULL; Node *slow,*fast; slow = fast = head; //先判斷是否存在環(huán) while(fast != NULL && fast->next != NULL) { fast = fast->next->next; slow = slow->next; if(fast == slow) break; } if(fast != slow) return NULL; //不存在環(huán) fast = head; //快指針從頭開始走，步長變?yōu)? while(fast != slow) //兩者相遇即為入口點 { fast = fast->next; slow = slow->next; } return fast; }

?

7. 編程判斷兩個鏈表是否相交

題目描述：給出兩個單向鏈表的頭指針（如下圖所示），

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

解題思路：

直接循環(huán)判斷第一個鏈表的每個節(jié)點是否在第二個鏈表中。但，這種方法的時間復雜度為O(Length(h1) * Length(h2))。顯然，我們得找到一種更為有效的方法，至少不能是O（N^2）的復雜度。

針對第一個鏈表直接構造hash表，然后查詢hash表，判斷第二個鏈表的每個節(jié)點是否在hash表出現(xiàn)，如果所有的第二個鏈表的節(jié)點都能在hash表中找到，即說明第二個鏈表與第一個鏈表有相同的節(jié)點。時間復雜度為為線性：O(Length(h1) + Length(h2))，同時為了存儲第一個鏈表的所有節(jié)點，空間復雜度為O(Length(h1))。是否還有更好的方法呢，既能夠以線性時間復雜度解決問題，又能減少存儲空間？

轉換為環(huán)的問題。把第二個鏈表接在第一個鏈表后面，如果得到的鏈表有環(huán)，則說明兩個鏈表相交。如何判斷有環(huán)的問題上面已經(jīng)討論過了，但這里有更簡單的方法。因為如果有環(huán)，則第二個鏈表的表頭一定也在環(huán)上，即第二個鏈表會構成一個循環(huán)鏈表，我們只需要遍歷第二個鏈表，看是否會回到起始點就可以判斷出來。這個方法的時間復雜度是線性的，空間是常熟。

進一步考慮“如果兩個沒有環(huán)的鏈表相交于某一節(jié)點，那么在這個節(jié)點之后的所有節(jié)點都是兩個鏈表共有的”這個特點，我們可以知道，如果它們相交，則最后一個節(jié)點一定是共有的。而我們很容易能得到鏈表的最后一個節(jié)點，所以這成了我們簡化解法的一個主要突破口。那么，我們只要判斷兩個鏈表的尾指針是否相等。相等，則鏈表相交；否則，鏈表不相交。
所以，先遍歷第一個鏈表，記住最后一個節(jié)點。然后遍歷第二個鏈表，到最后一個節(jié)點時和第一個鏈表的最后一個節(jié)點做比較，如果相同，則相交，否則，不相交。這樣我們就得到了一個時間復雜度，它為O((Length(h1) + Length(h2))，而且只用了一個額外的指針來存儲最后一個節(jié)點。這個方法時間復雜度為線性O(N)，空間復雜度為O(1)，顯然比解法三更勝一籌。

解法四的代碼如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

//判斷兩個鏈表是否相交 bool isIntersect(Node *h1,Node *h2) { if(h1 == NULL || h2 == NULL) return false; //異常判斷 while(h1->next != NULL) { h1 = h1->next; } while(h2->next != NULL) { h2 = h2->next; } if(h1 == h2) return true; //尾節(jié)點是否相同 else return false; }

?

8. 擴展：鏈表有環(huán)，如何判斷相交

題目描述：上面的問題都是針對鏈表無環(huán)的，那么如果現(xiàn)在，鏈表是有環(huán)的呢?上面的方法還同樣有效么?

分析：如果有環(huán)且兩個鏈表相交，則兩個鏈表都有共同一個環(huán)，即環(huán)上的任意一個節(jié)點都存在于兩個鏈表上。因此，就可以判斷一鏈表上倆指針相遇的那個節(jié)點，在不在另一條鏈表上。

代碼如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

//判斷兩個帶環(huán)鏈表是否相交 bool isIntersectWithLoop(Node *h1,Node *h2) { Node *circleNode1,*circleNode2; if(!hasCircle(h1,circleNode1)) //判斷鏈表帶不帶環(huán)，并保存環(huán)內(nèi)節(jié)點 return false; //不帶環(huán)，異常退出 if(!hasCircle(h2,circleNode2)) return false; Node *temp = circleNode2->next; while(temp != circleNode2) { if(temp == circleNode1) return true; temp = temp->next; } return false; }

?

9. 擴展：兩鏈表相交的第一個公共節(jié)點

題目描述：如果兩個無環(huán)單鏈表相交，怎么求出他們相交的第一個節(jié)點呢？

分析：采用對齊的思想。計算兩個鏈表的長度 L1 , L2，分別用兩個指針 p1 , p2 指向兩個鏈表的頭，然后將較長鏈表的 p1（假設為 p1）向后移動L2 - L1個節(jié)點，然后再同時向后移動p1 , p2，直到?p1 = p2。相遇的點就是相交的第一個節(jié)點。

代碼如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

//求兩鏈表相交的第一個公共節(jié)點 Node* findIntersectNode(Node *h1,Node *h2) { int len1 = listLength(h1); //求鏈表長度 int len2 = listLength(h2); //對齊兩個鏈表 if(len1 > len2) { for(int i=0;i<len1-len2;i++) h1=h1->next; } else { for(int i=0;i<len2-len1;i++) h2=h2->next; } while(h1 != NULL) { if(h1 == h2) return h1; h1 = h1->next; h2 = h2->next; } return NULL; }

?

10. 總結

可以發(fā)現(xiàn)，在鏈表的問題中，通過兩個的指針來提高效率是很值得考慮的一個解決方案，所以一定要記住這種解題思路。記住幾種典型的鏈表問題解決方案，很多類似的題目都可以轉換到熟悉的問題再解決。

參考文獻

• 程序員編程藝術：第九章、閑話鏈表追趕問題
• 判斷單鏈表是否存在環(huán)，判斷兩個鏈表是否相交問題詳解
• 面試算法之鏈表操作集錦

轉載于:https://www.cnblogs.com/zhizhan/p/4549107.html

總結

以上是生活随笔為你收集整理的面试精选：链表问题集锦的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。