鏈表相關面試題

題一、 給定單鏈表，檢測是否有環。

使用兩個指針p1,p2從鏈表頭開始遍歷，p1每次前進一步，p2每次前進兩步。如果p2到達鏈表尾部，說明無環，否則p1、p2必然會在某個時刻相遇(p1==p2)，從而檢測到鏈表中有環。

題二、 給定兩個單鏈表(head1, head2)，檢測兩個鏈表是否有交點，如果有返回第一個交點。

如果head1==head2，那么顯然相交，直接返回head1。

否則，分別從head1,head2開始遍歷兩個鏈表獲得其長度len1與len2。假設len1>=len2，那么指針p1由head1開始向后 移動len1-len2步。指針p2=head2，下面p1、p2每次向后前進一步并比較p1p2是否相等，如果相等即返回該結點，否則說明兩個鏈表沒有 交點。

題三、 給定單鏈表(head)，如果有環的話請返回從頭結點進入環的第一個節點。

運用題一，我們可以檢查鏈表中是否有環。

如果有環，那么p1p2重合點p必然在環中。從p點斷開環，方法為：p1=p, p2=p->next, p->next=NULL。此時，原單鏈表可以看作兩條單鏈表，一條從head開始，另一條從p2開始，于是運用題二的方法，我們找到它們的第一個 交點即為所求。

題四、只給定單鏈表中某個結點p(并非最后一個結點，即p->next!=NULL)指針，刪除該結點。

辦法很簡單，首先是放p中數據,然后將p->next的數據copy入p中，接下來刪除p->next即可。

題五、只給定單鏈表中某個結點p(非空結點)，在p前面插入一個結點。

辦法與前者類似，首先分配一個結點q，將q插入在p后，接下來將p中的數據copy入q中，然后再將要插入的數據記錄在p中。

題六、給定單鏈表頭結點，刪除鏈表中倒數第k個結點。

使用兩個節點p1,p2，p1初始化指向頭結點，p2一直指向p1后第k個節點，兩個結點平行向后移動直到p2到達鏈表尾部(NULL),然后根據p1刪除對應結點。

【鏈表相關面試題】相關文章：

面試題與技巧07-12

華為面試題07-11

「MySQL」經典面試題07-11

c面試題08-04

采購面試題07-11

面試題集錦07-11

Java面試題07-12

SQL面試題07-12

Google 的瘋狂面試題07-11

java面試題五07-11