鏈表相關(guān)面試題

題一、 給定單鏈表，檢測(cè)是否有環(huán)。

使用兩個(gè)指針p1,p2從鏈表頭開始遍歷，p1每次前進(jìn)一步，p2每次前進(jìn)兩步。如果p2到達(dá)鏈表尾部，說(shuō)明無(wú)環(huán)，否則p1、p2必然會(huì)在某個(gè)時(shí)刻相遇(p1==p2)，從而檢測(cè)到鏈表中有環(huán)。

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

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

否則，分別從head1,head2開始遍歷兩個(gè)鏈表獲得其長(zhǎng)度len1與len2。假設(shè)len1>=len2，那么指針p1由head1開始向后 移動(dòng)len1-len2步。指針p2=head2，下面p1、p2每次向后前進(jìn)一步并比較p1p2是否相等，如果相等即返回該結(jié)點(diǎn)，否則說(shuō)明兩個(gè)鏈表沒(méi)有 交點(diǎn)。

題三、 給定單鏈表(head)，如果有環(huán)的話請(qǐng)返回從頭結(jié)點(diǎn)進(jìn)入環(huán)的第一個(gè)節(jié)點(diǎn)。

運(yùn)用題一，我們可以檢查鏈表中是否有環(huán)。

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

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

辦法很簡(jiǎn)單，首先是放p中數(shù)據(jù),然后將p->next的數(shù)據(jù)copy入p中，接下來(lái)刪除p->next即可。

題五、只給定單鏈表中某個(gè)結(jié)點(diǎn)p(非空結(jié)點(diǎn))，在p前面插入一個(gè)結(jié)點(diǎn)。

辦法與前者類似，首先分配一個(gè)結(jié)點(diǎn)q，將q插入在p后，接下來(lái)將p中的數(shù)據(jù)copy入q中，然后再將要插入的數(shù)據(jù)記錄在p中。

題六、給定單鏈表頭結(jié)點(diǎn)，刪除鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)。

使用兩個(gè)節(jié)點(diǎn)p1,p2，p1初始化指向頭結(jié)點(diǎn)，p2一直指向p1后第k個(gè)節(jié)點(diǎn)，兩個(gè)結(jié)點(diǎn)平行向后移動(dòng)直到p2到達(dá)鏈表尾部(NULL),然后根據(jù)p1刪除對(duì)應(yīng)結(jié)點(diǎn)。

【鏈表相關(guān)面試題】相關(guān)文章：

面試題與技巧07-12

華為面試題07-11

「MySQL」經(jīng)典面試題07-11

c面試題08-04

采購(gòu)面試題07-11

面試題集錦07-11

Java面試題07-12

SQL面試題07-12

Google 的瘋狂面試題07-11

java面試題五07-11