前言

上一節(jié)我們學(xué)習(xí)了鏈表的概念以及鏈表的實現(xiàn)，那么本節(jié)我們就來了解一下鏈表具體有什么用，可以解決哪些實質(zhì)性的問題，我們借用習(xí)題來加強對鏈表的理解，那么廢話不多說，我們正式進入今天的學(xué)習(xí)

單鏈表相關(guān)經(jīng)典算法OJ題1：移除鏈表元素

https://leetcode.cn/problems/remove-linked-list-elements/description/

題目詳情

題解

思路一：

要想解決這個題目，我們首先需要創(chuàng)建一個名為 pcur 的變量，用來遍歷整個鏈表，找到與 val 相等的值，當(dāng)我們找到了值為 val 的節(jié)點，我們不能直接釋放掉這個節(jié)點，這樣會導(dǎo)致后面的數(shù)據(jù)無法被找到，我們此時還需要定義一個變量 prev ，讓 prev 一只指向 pcur 的前一個節(jié)點。當(dāng)我們找到值為 val 的節(jié)點，該節(jié)點此時被 pcur 指向，我們需要用 pcur->next 來找到它的下一個節(jié)點，我們再次創(chuàng)建一個變量 next ，把 pcur->next 存入 next 變量中，并且把這個節(jié)點與 prev 所指向的節(jié)點連接起來，再釋放掉 pcur ，此時就完成了移除鏈表元素的功能

思路二：

我們重新創(chuàng)建一個鏈表 newHead 和新鏈表的尾節(jié)點指針 newTail ，我們在原鏈表中進行遍歷，將所有值不為 val 的節(jié)點尾插至新鏈表中去。

我們首先需要創(chuàng)建一個名為 pcur 的變量，用來遍歷整個鏈表，若找到的值不為 val ，則直接尾插到新鏈表的 newTail 后面去，同時讓 newTail 指針向后挪動，而 newHead 指針一直保持不變

假設(shè)我們用思路二來解決問題

我們想要完成該函數(shù)的功能，首先我們需要往函數(shù)中傳入兩個變量

1.鏈表的頭節(jié)點 struct ListNode* head

2. value 的取值?int val

在開始插入的時候我們還需要判斷鏈表當(dāng)前的情況，到底是為空還是不為空

如果鏈表為空的話，要將 newHead 和 newTail 都賦予 pcur，此時頭節(jié)點等于尾節(jié)點

如果鏈表不為空，newTail->next 要等于 pcur 而此時 newTail 變量要等于 newTail->next?

排查

此時我們再來考慮一下特殊情況，若是要移除的數(shù)據(jù)是鏈表的尾節(jié)點。

我們遍歷到原鏈表的倒數(shù)第二個數(shù)據(jù)的時候，倒數(shù)第二個數(shù)據(jù)的 next 指針指向了尾節(jié)點，即使不插入最后一個元素到新鏈表中，倒數(shù)第二個節(jié)點仍然可以通過它自身的 next 指針找到原鏈表的尾節(jié)點，此時就會導(dǎo)致代碼出現(xiàn)錯誤，原鏈表中的尾節(jié)點還是被插入到了新鏈表中去了

那么我們怎么才能在這種情況下不帶上最后一個節(jié)點呢？

當(dāng)我們找到并且尾插了倒數(shù)第二個節(jié)點的時候，我們此時把它的 next 指針賦予空指針 NULL，這樣他就找不到原鏈表的最后一個節(jié)點了

此時我們還要考慮到一個問題，因為題目中說了，列表的節(jié)點數(shù)目可以為0，若鏈表的節(jié)點個數(shù)為0時，此時我們就不能把 newTail 中的 next 指針設(shè)置為空指針，這樣就會造成對空指針進行解引用的問題

那么根據(jù)上述的邏輯以及注意事項的規(guī)避，我們可以寫出代碼如下：

typedef struct ListNode ListNode;struct ListNode* removeElements(struct ListNode* head, int val)
{//創(chuàng)建一個新鏈表ListNode * newHead, * newTail;newHead = newTail = NULL;//遍歷原鏈表ListNode* pcur = head;while (pcur){//找值不為 val 的節(jié)點，然后尾插到新鏈表中if (pcur->val != val){//鏈表為空if (newHead == NULL){newHead = newTail = pcur;}//鏈表不為空else{newTail->next = pcur;newTail = newTail->next;}}pcur = pcur->next;}if (newTail)newTail->next = NULL;return newHead;
}

我們在Leetcode官網(wǎng)檢測一下結(jié)果是否正確：

代碼成功的解決問題，該題目完成

單鏈表相關(guān)經(jīng)典算法OJ題2：反轉(zhuǎn)鏈表

題目詳情

題解

思路一：

我們可以創(chuàng)建一個新的鏈表，我們逐一的遍歷原鏈表，讓里面的每一個節(jié)點按順序頭插到新鏈表之中去，當(dāng)遍歷結(jié)束后，此時我們拿到的新鏈表就是反轉(zhuǎn)了以后的鏈表

思路二：

我們先創(chuàng)建三個變量：分別為 n1 n2 n3。我們先讓 n1 指向空指針，讓 n2 指向鏈表的頭節(jié)點，讓 n3 指向 n2 的下一個節(jié)點

要完成鏈表的反轉(zhuǎn)，我們需要按以下步驟操作：

1.先讓 n2 的 next 指針不再指向 n3 ，而是讓它指向 n1 （n1 初始的情況下為空指針）

2.我們再讓 n1 指向 n2 ，讓 n3 指向它的下一個節(jié)點

3.我們重復(fù)以上步驟，讓 n2 的 next 指針不再指向 n3 ，而是讓它指向 n1

4.一直重復(fù)以上步驟，當(dāng) n2 和 n3 已經(jīng)找不到節(jié)點了，此時我們可以跳出循環(huán)，現(xiàn)在 n1 指向的位置就是反轉(zhuǎn)以后鏈表的頭節(jié)點

5.因為原題目說了，鏈表可以為空，所以我們還需要判斷是否為空

此時我們來嘗試實現(xiàn)代碼：

typedef struct ListNode ListNode;struct ListNode* reverseList(struct ListNode* head)
{//判空if (head == NULL){return head;}//創(chuàng)建三個指針ListNode* n1, * n2, * n3;n1 = NULL, n2 = head, n3 = n2->next;while (n2){n2->next = n1;n1 = n2;n2 = n3;if (n3)n3 = n3->next;}return n1;
}

提醒：最后一次讓 n3 = n3->next 的代碼不能夠執(zhí)行，因為此時 n3 已經(jīng)是空指針了，不能對空指針進行解引用，所以我們需要對 n3 加以判斷

我們現(xiàn)在在Leetcode的官網(wǎng)運行一下代碼：

代碼成功的解決問題，該題目完成

單鏈表相關(guān)經(jīng)典算法OJ題3：鏈表的中間結(jié)點

題目

題解

思路一：

我們可以遍歷全鏈表，定義一個變量 count 用來計算遍歷的節(jié)點數(shù)，當(dāng)遍歷結(jié)束后直接返回 （count / 2）節(jié)點，則該節(jié)點就是鏈表的中間節(jié)點

思路二：（快慢指針）

我們首先分為奇數(shù)個和偶數(shù)個兩種情況

我們先定義兩個變量，一個叫做 slow 指針，一個叫做 fast 指針，我們讓 slow 指針每次走一步，fast 指針一次走兩步，2slow = fast

1.若鏈表的節(jié)點數(shù)為奇數(shù)個，當(dāng) fast->next 指針指向到 NULL 指針時，此時 slow 指針剛好指向鏈表的中間節(jié)點

2.若鏈表的節(jié)點數(shù)為偶數(shù)個，當(dāng) fast 指針指向到 NULL 指針時，此時 slow 指針剛好指向鏈表的中間節(jié)點

有了這個思想以后，我們試著寫出代碼：

typedef struct ListNode ListNode;struct ListNode* middleNode(struct ListNode* head) 
{//創(chuàng)建快慢指針ListNode* slow = head;ListNode* slow = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;}//此時slow剛好指向中間節(jié)點return slow;}

我們在 Leetcode 的官網(wǎng)運行一下代碼，看看結(jié)果

代碼成功的解決問題，該題目完成

結(jié)尾

本節(jié)我們了解了鏈表在題目中的應(yīng)用，下一節(jié)同樣給大家細(xì)細(xì)講解鏈表在題目中的應(yīng)用，幫助大家更好的理解鏈表，那么本節(jié)的內(nèi)容就到此為止了，謝謝您的瀏覽！！！