鏈表相關的面試題型總結

鏈表相關的面試題型總結及其個別實現

對指針的掌握程度，是衡量一個程序員的基本功是否扎實的重要考量標准。而數據結構中的鏈表、二叉樹等基本數據結構，是考核指針的最佳利器。本文稍微總結了下鏈表的主要考點，以備未來的求職。

說在前面的注意事項

首先，涉及到指針的編程，對於指針有效性的判斷不可忽視，代碼中一定要有對NULL指針的判斷，這樣代碼才更加的魯棒。 其次，若對鏈表進行插入，刪除操作，一定要注意更新head指針（和tail指針）的指向。 最後，我們定義結點的數據結構為： struct Node{
int datum;
Node next;
};

先總結下我的心得

首先，若是題目對空間復雜度沒有什麼要求，可以借鑒hash，額外的數組等，將問題簡化 其次，可以使用快慢指針的思想，設置兩個指針，一個指針走得快些或先走幾步，就能夠很好的解決大多數問題。 再者，對於指針的訪問操作，一定要小心再小心，一定要確認有效才能繼續訪問。 最後，涉及到修改頭指針指向的操作（插入，刪除，排序等），函數中傳入的指針參數要設置成 Node**， 這樣才能進行修改操作。

常考的題型

對於鏈表， 主要考核以下幾類部分：

一、查詢判斷類

二、操作類

問題分析及求解

1.1. 兩鏈表(無環)相交的判定

 

 

思路一：尾地址判定法。常規的判斷方法是判斷兩鏈表的一個結點地址是否相同。具體做法是先遍歷list1, 保存最後一個結點的地址end1；再遍歷list2到最後一個結點，判斷地址是否等於end1。 時間復雜度為O(len1+len2)， 空間復雜度為 O(1)。
View Code

 

思路二：hash地址法。通常若允許使用hash的話，能夠快速有效的解決。 這裡，我們遍歷list1, 將每個結點的地址hash；再遍歷list2，判斷結點地址是否出現在hash表中。時間復雜度為O(len1+len2)， 空間復雜度為O(len1); 這裡，雖然時間復雜度未降低，同時增加了空間復雜度，但是卻能很好的解決第1個公共結點問題。算是一種補償。

 

思路三：鏈接成環法。參考下面圖3。首先，先將第一個鏈表的最後一個結點鏈接到第二個結點的頭，然後判斷是否有環，若有環，則說明兩個鏈表存在公共結點。

1.2. 鏈表是否有環的判定

 

思路一： 快慢指針法. 我們在用快fast， slow兩指針指向鏈表頭，fast指針一次跨兩步， slow指針一次跨一步，有環的條件為fast==slow ！= NULL 。
View Code 思路二： hash地址法。遍歷鏈表，將地址hash進來，若NULL了，則說明無環，若存在相同的地址，則說明有環。 且能得到第一個入環的點。時間復雜度為O(len1)， 空間復雜度為O(len1)。

1.3. 尋找兩鏈表的第一個公共結點

思路一：hash地址法。通過1.1的分析，我們能夠用hash的方法快速得到第一個公共的結點。 思路二：首尾對齊法。若采用尾地址判定法，我們能夠得到最後一個公共結點，那麼回溯N步同時判斷地址是否相等，就能得到第一個公共結點了。可惜是單鏈表，沒有prev指針，但是這個思想啟發了我們，若是兩個鏈表尾對齊了，那麼對長鏈表先next X 步，使頭部也對齊，那麼，第一個相同的地址點，就是第一個公共結點了。根據 圖3, 我們可以看出，長鏈表先走X=(lenMax-lenMin)步後，那麼，他們將同時遞增到first common 點。時間復雜度為O(len1+len2+x)， 空間復雜度為O(1)。

Node* cross_first(Node* h1, Node*(h1==NULL || h2==* p = s1 = (p->next !=++= p->* q = s2 = (q->next !=++= q->(p !=== prestep = static_cast<>(abs(s1-(s1>(prestep--= p->(prestep--= q->(p !== p->= q->

思路三：鏈接成環法(也是求環的入口點的解法)。將鏈表1的尾結點鏈接到鏈表2的第一個結點，然後調用快慢指針法判斷是否有環。然後保存相遇點，同時slow指針從頭開始,步長為1遞增；fast指針從相遇點開始，步長為1遞增，他們再一次的相遇點，則是第一個公共結點。 數學推導如下： 先假設鏈表長 L, 入環前結點數 b, 環內結點 r, slow指針走了 s 步相遇， 相遇點為環內 x 步， 則 fast 指針走了 2s 步， 且相遇點前fast已近走了n（n>=1） 圈。 則有： snr
s nr
s b x
r L b;
b x nr (n)r r (n)r L b
(n)r 這裡，L-b-x 等於相遇點到環結尾的長度，b 為開頭到環入口的長度。因此，在鏈表頭和相遇點各設置一個指針，繼續走 b 步，就肯定能相遇。

Node* cross_first_by_circle(Node* h1, Node*(h1 == NULL || h2 == NULL) * p =(p->next !== p->* holdh1 =->next =* fast ==(fast == NULL) * slow =(fast !== fast->= slow->->next =

參考資料： http://www.cnblogs.com/gw811/archive/2012/10/28/2743182.html http://wenku.baidu.com/view/299c440cf78a6529647d536b.html 《劍指offer》

1.4 求鏈表的倒數第K個數

有了前面首尾對齊法和快慢指針的思想，我們是不是能啟發到怎麼求倒數第K個數呢？ 思路一： 若是雙向鏈表，則很簡單，從尾端往回走K步就行。 思路二： 若是單鏈表，先遍歷得到鏈表的長度，然後逆推出要到倒數k位置，則要走 n-k+1步； 思路三： 很簡單，設置兩個指針，一個指針從從頭先走k-1步，另外個指針再從頭開始，那麼，當第一個指針到達結尾時，另外個指針恰好到達倒數第K個結點。

Node* backK(Node* head, (head == NULL || k <= ) * p =( i=; i<k-; ++(p->next == NULL) = p->* knode =(p->next !== p->= knode->

歸納法證明： 若k=1: k-1 = 0, 兩個指針同步運行，成立。 若k=x; k-1 = x-1; 第一個指針繼續走 n-x步到達最後一個結點， 第二個指針走 (n-x) 步後，處於倒數 n-(n-x)=x 的位置，成立。 這裡的注意事項是： 若鏈表長度小於k怎麼辦？ 輸入的是空鏈表怎麼辦？若輸入k=0， 則k-1步導致溢出怎麼辦？因此，寫好一個好的代碼是要考慮很多因素的。

2.1 鏈表排序

對鏈表排序，想下似乎挺簡單的，實際上是很富有挑戰性的。這裡我們以單鏈表為例。 思路一： 若是空間非常富裕的話，我們完全可以借鑒STL中對deque進行排序時候的做法，先將元素賦值到vector中，排序後再拷貝回deque。 做法也是一樣的，遍歷鏈表，把每個元素存入到一個新的數組中，然後對該數組排序（默認使用快排），然後再拷貝回鏈表（只修改衛星數據）。時間復雜度為O(n++n) = O(nlgn)， 空間復雜度為O(n)； 思路二： 單鏈表，只能前向移動，我們考慮到簡單的排序方法必須是相鄰進行比較的，符合條件的有插入排序，冒泡排序，甚至，希爾排序也是可以的。同時，排序算法內部的循環也必須是前向移動才行。
對於思路二，我們有兩種想法，交換指針or交換數據域。
我們先做下簡單的，不交換指針，只交換衛星數據，這樣，代碼就很容易實現。 下面代碼實現了冒泡排序和插入排序。和常規的解法不同的是，內循環是頭比到尾的，同時采用了STL的[ ) 方式來實現，NULL真是個好哨兵呀。

  insert_sort(Node* head,Node* end =       (head == end)       Node* piot = head->     Node* cur =          (piot !=         cur =         ( (cur!=piot) && (cur->datum<=piot->             cur = cur->          tmp = cur->         cur->datum = piot->         piot->datum =         piot = piot->   
  bubble_sort(Node* head, Node* end =      (head == end)      Node* piot =     Node*     Node*           change =      (piot !=         cur = piot->         prev =         change =          (cur !=             (cur->datum < prev->                 tmp = cur->                 cur->datum = prev->                 prev->datum =                 change =               prev =             cur = cur->          piot = piot->         ( !change )   }

 

對於交換指針來說，想下是好恐怖的一件事呀。其實不難，把結點交換的函數抽取出來，問題就簡單了

首先，我們要設計一下鏈表節點的交換函數 swap_point， 這個函數的聲明如下：

  swap_point(Node**                 Node* preFirst, Node* Node* preSecond, Node*

然後，要考慮兩大種情況的組合：

• first 是否為頭結點？
• first->next 是否等於 second ?

對於頭結點問題，我們知道這是鏈表問題必須考慮的，我們在代碼中加個判斷語句，選擇性執行頭結點的更新就行。

對於first->next 是否等於 second ，大家畫圖下，就很好理解了：

接著，我們在插入排序中，在要交換的位置傳入合適的前向指針，就行，哈哈，代碼如下：

  swap_point(Node** head, Node* preFirst, Node* first, Node* preSecond, Node*      (head == NULL || *head == NULL || first == NULL || second == NULL)      (first->next !=         Node* tmp = first->         first->next = second->         second->next =         preSecond->next =     }         first->next = second->         second->next =      (*head !=         preFirst->next =     
         *head =  
  insert_sort_point(Node** head, Node* end =      (*head == end)      Node* piot = (*head)->     Node* prepiot = *     Node* cur = *     Node* precur = *     (piot !=         cur = *         ((cur != piot) && (cur->datum<=piot->             precur =             cur = cur->           prepiot =         piot = piot->  }

經過測試，成立！

2.2 鏈表插入

對於鏈表插入操作，分為頭插法和尾插法。 若是排序好的鏈表插入，還要定位到相應的位置。

 Node* insert_front(Node** head,       (head ==              (*head ==         *head =      }         Node* p =          p->next = *         *head =       *  Node* insert_comp(Node** head,        (head ==              Node*       (*head ==          =          *head =      }          =          ((*head)->datum >          }             Node* p = *             Node* n = (*head)->             ( n != NULL && n->datum <                 p =                 n = n->              p->next =              ->next =         }

2.3 鏈表刪除某一節點

對於刪除操作，簡單的來說，就是兩個指針，一前一後，後的一個到達刪除點後，操作就很簡單了。還有個方法，見2.4.

2.4 單位時間內刪除節點（節點指針給定）

對於這個，一般通常的做法是采用2.3的做法，但是這個時間復雜度為O(n)。 可以參考下<劍指offer>中介紹的方法，我們先畫圖來說下：

  圖4的上半部分是我們通常(2.3)的做法，需要前一個指針輔助刪除； 圖4下半部分的刪除，就不需要了。做法如下： 首先來個輔助指針q指向下一個結點。 將q的數據域賦給cur, 然後更新cur.next， 最後刪除q。 這樣，就能在O(1)的時間內刪除結點了。

  delNode(Node** head, Node*      (head == NULL || *head == NULL || n ==              (n->next != NULL){ 
         Node* tmp = n->         n->datum = tmp->         n->next = tmp->          tmp =     } (*head == n){   
          *head =     }{                    
         Node* p = *         (p->next !=             p = p->          p->next =          n =  }

2.5 有序鏈表合並

這個可以參考下STL中的接合函數的寫法。

2.6 復雜鏈表復制

參考下<劍指offer>

測試函數：
打印函數

 #include 
 #include <iostream>
         Node* head1 =     insert_comp (&head1,      insert_comp (&head1,      insert_comp (&head1,      insert_comp (&head1,      insert_comp (&head1,      Node* head2 = insert_comp (&head1,     insert_front(&head2,     insert_front(&head2,       cout <<  << cross_tail_compare (head1,head2) <<     cout <<  << cross_first (head1,head2)->datum <<     cout <<  << cross_first_by_circle (head1,head2)->datum <<     cout <<  << backK (head1,)->datum <<     Node* pp =     (pp ==         cout <<  <<     }         cout <<  <<      cout <<  <<     Node* head3 =     insert_comp (&head3,      insert_comp (&head3,      Node* circin = insert_comp (&head3,      insert_comp (&head3,      Node* tail = insert_comp (&head3,      tail->next =      show(tail,tail->     pp =     (pp ==         cout <<  <<     }         cout <<  <<        }