三道鏈表經(jīng)典面試題
鏈表在工作中是很常用的數(shù)據(jù)結(jié)構(gòu)也是面試必考的數(shù)據(jù)結(jié)構(gòu)，對(duì)于鏈表一定要能靈活運(yùn)用方能快速回答出面試官提的問題，并且經(jīng)常要求現(xiàn)場(chǎng)手寫代碼，這里我總結(jié)了單鏈表三道經(jīng)典面試題并以源碼的形式呈現(xiàn)解決方案。
01
—
翻轉(zhuǎn)單鏈表
翻轉(zhuǎn)鏈表基本上是最簡(jiǎn)單的鏈表相關(guān)面試/筆試題了，核心思想則是：
用一個(gè)局部變量存儲(chǔ)鏈表頭
從第二個(gè)結(jié)點(diǎn)開始遍歷單鏈表
將當(dāng)前遍歷的結(jié)點(diǎn)采用頭插法插入新鏈表
這里我們將會(huì)用到我前面的文章所實(shí)現(xiàn)的單鏈表，還不會(huì)寫單鏈表的同學(xué)請(qǐng)參考這篇文章，我們先看一下翻轉(zhuǎn)鏈表的函數(shù)聲明。
extern list_t *convert_list(list_t *list); //翻轉(zhuǎn)鏈表我們需要傳入鏈表頭結(jié)點(diǎn)，返回值則是翻轉(zhuǎn)后的鏈表頭結(jié)點(diǎn)。函數(shù)實(shí)現(xiàn)代碼如下：
list_t *convert_list(list_t *list){
if(list == NULL){
return NULL;
}
list_t *head = list; //新鏈表頭結(jié)點(diǎn)
list_t *temp = NULL;
list = list->next;
head->next = NULL;
while(list != NULL){
temp = list; //保存遍歷過的結(jié)點(diǎn)
list = list->next; //遍歷下一個(gè)結(jié)點(diǎn)
temp->next = head; //頭查法插入鏈表
head = temp; //更新鏈表頭結(jié)點(diǎn)
}
return head;
}—
查找單鏈表倒數(shù)第k個(gè)結(jié)點(diǎn)
查找倒數(shù)第k個(gè)結(jié)點(diǎn)的方法有很多，比如先遍歷到鏈表尾部，如果鏈表的長(zhǎng)度length小于k那么k值是非法的則找不到結(jié)點(diǎn)，若k值是合理的，再往前遍歷到第k個(gè)結(jié)點(diǎn)即可。或者求出鏈表長(zhǎng)度length，如果length小于k那么k值是非法的則找不到結(jié)點(diǎn)，否則再遍歷到第length - k個(gè)結(jié)點(diǎn)，以上兩種方法都要遍歷2次，而且也是我們下意識(shí)就能想到的，很顯然面試官基本不會(huì)這么考你，那么有沒有一種只需要遍歷一遍就能找到單鏈表倒數(shù)第k個(gè)結(jié)點(diǎn)的方法呢？
現(xiàn)在有一種方法能解決這個(gè)問題，核心思想則是：
需要2個(gè)指針，指針1先行遍歷，直到指針1遍歷到第k個(gè)結(jié)點(diǎn)時(shí)，指針2從鏈表頭開始遍歷。
指針1遍歷到尾部的時(shí)候，指針2指向的結(jié)點(diǎn)就是倒數(shù)第k個(gè)結(jié)點(diǎn)。
函數(shù)聲明如下：
extern list_t *get_last_k_node(list_t *list, int k); //獲取倒數(shù)第K個(gè)結(jié)點(diǎn)list_t *get_last_k_node(list_t *list, int k){
if(list == NULL || k <= 0){
return NULL;
}
int index = 0;
list_t *head = list;
while(list != NULL){
index++;
list = list->next;
if(index > k){
//前一個(gè)指針已經(jīng)移動(dòng)了k個(gè)結(jié)點(diǎn)，則后一個(gè)指針開始移動(dòng)
//直到前一個(gè)指針已經(jīng)移動(dòng)到鏈表尾部，則后一個(gè)指針指向的就是倒數(shù)第k個(gè)結(jié)點(diǎn)
head = head->next;
}
}
//k值不正確，則找不到目標(biāo)結(jié)點(diǎn)
if(index < k){
return NULL;
}
return head;
}—
判斷單鏈表是否有環(huán)
定義2個(gè)指針，一個(gè)快指針，一個(gè)慢指針。
快指針先從鏈表頭開始遍歷，快指針移動(dòng)后，緊接著慢指針移動(dòng)，快指針每次移動(dòng)2個(gè)結(jié)點(diǎn)，慢指針每次移動(dòng)1個(gè)結(jié)點(diǎn)。
檢查快指針是否等于慢指針（快指針追趕上了慢指針）。有則代表有環(huán)，反之如果快指針已經(jīng)到達(dá)鏈表尾部則無環(huán)。
因?yàn)槲覀冊(cè)?a target="_blank" data-itemshowtype="0" tab="innerlink" data-linktype="2">上一篇文章中只實(shí)現(xiàn)了無環(huán)單鏈表，為了測(cè)試需要我們定義一個(gè)將無環(huán)單鏈表轉(zhuǎn)成有環(huán)單鏈表函數(shù)函數(shù)定義如下。
extern list_t *transfer_to_ring_list(list_t *list); //將單鏈表轉(zhuǎn)成環(huán)形鏈表實(shí)現(xiàn)代碼如下：
list_t *transfer_to_ring_list(list_t *list){
if(list == NULL){
return NULL;
}
list_t *head = list;
while(list->next != NULL){
list = list->next;
}
list->next = head;
return head;
}extern bool is_there_a_ring(list_t *list); //判斷鏈表是否有環(huán)bool is_there_a_ring(list_t *list){
if(list == NULL){
return false;
}
list_t *node = list;
while(list != NULL){
if(list->next != NULL){
list = list->next->next; //首指針移動(dòng)2個(gè)結(jié)點(diǎn)
//兩個(gè)指針相遇說明鏈表有環(huán)
if(list == node){
return true;
}
}else{
break;
}
if(node != NULL){
node = node->next; //后面的指針移動(dòng)一個(gè)結(jié)點(diǎn)
}
}
return false;
}—
結(jié)果驗(yàn)證
最后我們寫一個(gè)小程序驗(yàn)證三道單鏈表經(jīng)典面試題代碼是否正確，代碼如下：
#include <stdio.h>
#include "list.h"
#include "list_opt.h"
int main() {
int i = 0;
list_t *list = new_list_node(0);
for(i = 0; i < 15; i++){
list = list_add(list, i + 1);
}
printf("初始完整鏈表數(shù)據(jù)\n");
list_print(list);
list_t *node = get_last_k_node(list, 3); //找到倒數(shù)第3個(gè)結(jié)點(diǎn)
if(node != NULL){
printf("倒數(shù)第3個(gè)結(jié)點(diǎn)的值是：%d\n", node->data);
}else{
printf("k值不正確找不到目標(biāo)結(jié)點(diǎn)\n");
}
list = convert_list(list); //翻轉(zhuǎn)鏈表
printf("鏈表翻轉(zhuǎn)后的數(shù)據(jù)\n");
list_print(list);
list = transfer_to_ring_list(list); //將單鏈表轉(zhuǎn)成環(huán)形鏈表
bool have_ring = is_there_a_ring(list); //判斷鏈表是否有環(huán)
if(have_ring){
printf("鏈表有環(huán)\n");
}else{
printf("鏈表無環(huán)\n");
}
printf("新建無環(huán)鏈表\n");
list_t *list2 = new_list_node(20);
for(i = 0; i < 5; i++){
list2 = list_add(list2, i + 21);
}
have_ring = is_there_a_ring(list2); //判斷鏈表是否有環(huán)
if(have_ring){
printf("鏈表有環(huán)\n");
}else{
printf("鏈表無環(huán)\n");
}
return 0;
}編譯運(yùn)行輸出：
初始完整鏈表數(shù)據(jù)
15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0,
倒數(shù)第3個(gè)結(jié)點(diǎn)的值是：2
鏈表翻轉(zhuǎn)后的數(shù)據(jù)
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
鏈表有環(huán)
新建無環(huán)鏈表
鏈表無環(huán)代碼運(yùn)行正確。