上一階段的字符串系列之后很長(zhǎng)時(shí)間都沒(méi)有更新文章咖为，現(xiàn)在接著來(lái)，本階段是鏈表系列的凯旭，鏈表系列的算法題我不會(huì)再用大量篇幅寫(xiě)一個(gè)問(wèn)題的解決方案篡石，針對(duì)一個(gè)問(wèn)題寫(xiě)一個(gè)解決方案芥喇，所以篇幅會(huì)小很多。這篇文章會(huì)介紹和鏈表相關(guān)的簡(jiǎn)單算法題凰萨，后面還會(huì)介紹復(fù)雜算法題继控。
- 添加/刪除結(jié)點(diǎn)
- 從尾到頭打印鏈表
- 翻轉(zhuǎn)單鏈表
- 在O(1)時(shí)間內(nèi)刪除鏈表結(jié)點(diǎn)
1.添加/刪除結(jié)點(diǎn)
我們都知道，鏈表的添加和刪除操作相比數(shù)組是很方便的胖眷，因?yàn)殒湵聿灰蠼Y(jié)點(diǎn)的物理順序和邏輯順序相同武通，所以添加刪除結(jié)點(diǎn)的時(shí)候不需要像數(shù)組一樣移動(dòng)大量的結(jié)點(diǎn)，借助指針珊搀，修改指針指向冶忱，我們就可以很方便的實(shí)現(xiàn)添加和刪除結(jié)點(diǎn)的操作。
添加/刪除結(jié)點(diǎn)是鏈表類算法題中比較簡(jiǎn)單的操作了境析，不會(huì)有太大問(wèn)題囚枪。主要是在注意細(xì)節(jié)，添加/刪除的時(shí)候要注意判斷鏈表是否為空劳淆，如果鏈表為空链沼，就要修改頭指針的指向，也就是修改頭指針指向的地址沛鸵。
代碼
鏈表的數(shù)據(jù)結(jié)構(gòu)的定義：
注意：這些聲明中包含了一個(gè)自引用結(jié)構(gòu)的列子括勺。在定義結(jié)構(gòu)ListNode之前，已經(jīng)定義了指向該結(jié)構(gòu)的指針曲掰。C語(yǔ)言允許定義指向尚不存在的類型的指針疾捍。
typedef struct ListNode *list_pointer;
typedef struct ListNode
{
int value;
list_pointer link;
};
list_pointer pHead;
在鏈表尾添加節(jié)點(diǎn)
有在前端，中間插入結(jié)點(diǎn)的栏妖，也有在尾部乱豆，這里的例子是在鏈表尾插入結(jié)點(diǎn)。注意吊趾，如果鏈表為空咙鞍，那么添加結(jié)點(diǎn)需要修改頭指針的指向房官，所以這里接收的參數(shù)是頭指針的地址。
//pHead是指向指針的指針 ListNode** p
void addToTail(list_pointer *pHead, int value){
list_pointer node = (list_pointer)malloc(sizeof(ListNode));
if (node == NULL)
{
fprintf(stderr, "Faile\n");
exit(1);
}
node->value = value;
node->link = NULL;
if (*pHead == NULL)
{
*pHead = node;
}
else{
list_pointer p = *pHead;
while (p->link != NULL){
p = p->link;
}
p->link = node;
}
}
刪除中間結(jié)點(diǎn)：
刪除指定值的結(jié)點(diǎn)续滋，我們不知道該結(jié)點(diǎn)在什么位置翰守，所以需要遍歷鏈表找到結(jié)點(diǎn)。
//如果刪除首節(jié)點(diǎn)疲酌，那么需要改變首節(jié)點(diǎn)指針的指向
bool deleteNode(list_pointer *pHead, int value){
if (*pHead == NULL)
{
fprintf(stderr, "The linklist is empty!\n");
exit(1);
}
ListNode *node = NULL;
if ((*pHead)->value == value){//刪除首節(jié)點(diǎn)
node = *pHead;
*pHead = (*pHead)->link;
free(node);
return true;
}
else{
list_pointer p = *pHead;
while (p->link != NULL && p->link->value != value){
p = p->link;
}
if (p->link != NULL && p->link->value == value)
{
node = p->link;
p->link = p->link->link;
free(node);
}
}
}
2.從尾到頭打印鏈表
看到這到道題的第一反應(yīng)是從頭到尾打印鏈表會(huì)比較簡(jiǎn)單蜡峰，所以我們可以改變鏈表的指針指向，但是這樣會(huì)改變鏈表原來(lái)的結(jié)構(gòu)朗恳，是否允許改變鏈表的結(jié)構(gòu)湿颅，這個(gè)取決于面試官。這里的例子是不改變鏈表結(jié)構(gòu)粥诫。
算法思想
從尾到頭打印鏈表也就是說(shuō)先存入的元素后輸出油航，后存入的先輸出，和椈辰“后進(jìn)先出”的思想一樣谊囚，所以我們可以在遍歷鏈表的時(shí)候先將元素存入棧中，再循環(huán)遍歷棧輸出元素执赡。
想到了使用棧镰踏，而遞歸的本質(zhì)就是使用棧存儲(chǔ)，那么我們使用遞歸也能實(shí)現(xiàn)同樣的效果沙合，下面的例子就是用遞歸實(shí)現(xiàn)的奠伪。
代碼：
void PrintListReversingly(list_pointer pHead) {
list_pointer p = pHead;
if (p) {
if (p->link) {
PrintListReversingly(p->link);
}
printf("鏈表元素：%d\n", p->value);
}
}
使用遞歸代碼會(huì)簡(jiǎn)潔很多，但是當(dāng)鏈表非常長(zhǎng)的時(shí)候首懈，函數(shù)調(diào)用的層級(jí)會(huì)很深绊率，可能會(huì)導(dǎo)致函數(shù)調(diào)用棧溢出，顯式的使用椌柯模基于循環(huán)來(lái)遍歷的魯棒性會(huì)好一些滤否。
3.翻轉(zhuǎn)單鏈表
題目：寫(xiě)一個(gè)函數(shù)，輸入鏈表的頭結(jié)點(diǎn)挎袜，翻轉(zhuǎn)該鏈表，并返回翻轉(zhuǎn)后的鏈表的頭結(jié)點(diǎn)肥惭。
算法思想
看上面的圖盯仪，如果是對(duì)結(jié)點(diǎn)i翻轉(zhuǎn)鏈表，就是改變i的link的指向蜜葱，將它指向前一個(gè)結(jié)點(diǎn)h全景，但是這樣會(huì)導(dǎo)致i指向j的鏈丟失，所以我們需要存儲(chǔ)下這個(gè)值牵囤，也就是說(shuō)爸黄，在一次改變指針指向的操作中滞伟，我們需要存儲(chǔ)下前一個(gè)結(jié)點(diǎn)h，后一個(gè)結(jié)點(diǎn)j炕贵，和當(dāng)前結(jié)點(diǎn)i梆奈。此外，我們還需要明確称开，在翻轉(zhuǎn)了鏈表之后亩钟，原來(lái)的頭結(jié)點(diǎn)變成了尾結(jié)點(diǎn)，而現(xiàn)在的尾節(jié)點(diǎn)呢鳖轰，就是NULL清酥。分析完這些之后很容易寫(xiě)出代碼。
代碼
//翻轉(zhuǎn)鏈表
list_pointer Invert(list_pointer pHead)
{
list_pointer middle, trail;
middle = NULL;
//當(dāng)pHead指向原鏈表的最后一個(gè)結(jié)點(diǎn)的link時(shí)蕴侣，退出循環(huán)
//此時(shí)middle剛好指向原鏈表的最后一個(gè)結(jié)點(diǎn)
while (pHead) {
trail = middle;
middle = pHead;//此時(shí)middle和pHead指向的地址相同
pHead = pHead->link;
middle->link = trail;
}
return middle;
}
4.在O(1)時(shí)間內(nèi)刪除鏈表結(jié)點(diǎn)
常規(guī)的思維焰轻，刪除鏈表結(jié)點(diǎn)需要知道它的前一個(gè)結(jié)點(diǎn)，簡(jiǎn)單的三句代碼昆雀，就是判斷p->link->value == value辱志，然后修改p->link = p->link->link，釋放p->link.這樣就需要遍歷鏈表忆肾，知道要?jiǎng)h除的結(jié)點(diǎn)的前一個(gè)荸频，時(shí)間復(fù)雜度為O(n)。如果換一種思路呢客冈？
算法思想
假設(shè)結(jié)點(diǎn)h,i,j是鏈表中相鄰的3個(gè)結(jié)點(diǎn)旭从，現(xiàn)在要?jiǎng)h除i，可以進(jìn)行下面3步：
- 將結(jié)點(diǎn)j的值復(fù)制到結(jié)點(diǎn)i上场仲；
- 修改i的link和悦；
- 釋放結(jié)點(diǎn)j。
現(xiàn)在需要考慮一下特殊情況下是否也滿足渠缕。當(dāng)刪除的節(jié)點(diǎn)是頭結(jié)點(diǎn)時(shí)鸽素，需要修改頭結(jié)點(diǎn)的link指針。當(dāng)刪除的是尾結(jié)點(diǎn)時(shí)亦鳞，它沒(méi)有下一個(gè)結(jié)點(diǎn)馍忽，所以需要遍歷鏈表，得到它的前一個(gè)結(jié)點(diǎn)燕差。當(dāng)鏈表只有一個(gè)結(jié)點(diǎn)時(shí)遭笋，刪除的結(jié)點(diǎn)是頭結(jié)點(diǎn)（尾節(jié)點(diǎn)），需要將頭指針的指向置為NULL徒探。
代碼
//在O(1)內(nèi)刪除一個(gè)結(jié)點(diǎn)
void DeleteNode(list_pointer *pHead, ListNode *node)
{
if (!(*pHead) || !node)
return;
//要?jiǎng)h除的不是尾結(jié)點(diǎn)
if (node->link)
{
ListNode *pNext = node->link;
node->value = pNext->value;
node->link = pNext->link;
free(pNext);
}
//鏈表中只有一個(gè)結(jié)點(diǎn)刪除頭結(jié)點(diǎn)瓦呼，也是尾結(jié)點(diǎn)
else if (*pHead == node)//node->link為NULL
{
free(node);
*pHead = NULL;
}
else//鏈表中有多個(gè)結(jié)點(diǎn)，刪除的是尾結(jié)點(diǎn)
{
list_pointer p = *pHead;
while (p->link != node)
{
p = p->link;
}
p->link = NULL;
free(node);
}
}
總結(jié)
這些題難度都不大测暗，使用指針很靈活央串，但是也很容易出錯(cuò)磨澡，主要是關(guān)注細(xì)節(jié)。這篇就到這里了质和，不足之處稳摄，還請(qǐng)多指教~
