1. 移除鏈表元素

????????OJ鏈接：力扣（LeetCode）官網(wǎng) - 全球極客摯愛(ài)的技術(shù)成長(zhǎng)平臺(tái)

????????本題是說(shuō)給出一個(gè)鏈表的頭節(jié)點(diǎn)head和一個(gè)整數(shù)val，如果發(fā)現(xiàn)節(jié)點(diǎn)中存的數(shù)據(jù)有val就刪掉它，最后返回修改后的鏈表頭節(jié)點(diǎn)地址

????????如果題目中沒(méi)有明確提及給出的鏈表是否是帶頭的，那就默認(rèn)是不帶頭的鏈表，此時(shí)題目中再提到頭節(jié)點(diǎn)就是指鏈表的第一個(gè)節(jié)點(diǎn)

思路1：

????????從第二個(gè)節(jié)點(diǎn)開(kāi)始，判斷其內(nèi)含的數(shù)據(jù)是否是val，然后遍歷鏈表，最后判斷頭節(jié)點(diǎn)中數(shù)據(jù)是否是val，如果是，再挪移頭節(jié)點(diǎn)的指向

????????至于為什么從第二個(gè)節(jié)點(diǎn)開(kāi)始掃描是為了不用每次都判斷一下頭節(jié)點(diǎn)要不要移動(dòng)，先把后面的節(jié)點(diǎn)都處理好，最后再確定頭節(jié)點(diǎn)的指向

????????但是這個(gè)思路還是太復(fù)雜了

思路2：

????????創(chuàng)建一個(gè)新鏈表，把不是val的節(jié)點(diǎn)都丟到新鏈表中去，最后返回新鏈表的頭節(jié)點(diǎn)

????????與其說(shuō)是創(chuàng)建了一個(gè)新鏈表，不如說(shuō)是將原鏈表的鏈接順序拿到一個(gè)新的地方進(jìn)行更改

struct ListNode* removeElements(struct ListNode* head, int val) 
{//記錄新鏈表的頭和尾struct ListNode* newhead = NULL;struct ListNode* newtail = NULL;//pcur用來(lái)掃描原鏈表struct ListNode* pcur = head;while (pcur){//不是val尾插到新鏈表的尾if (pcur->val != val){//如果新鏈表為空，那么新加入的節(jié)點(diǎn)既是頭節(jié)點(diǎn)也是尾節(jié)點(diǎn)if (newhead == NULL){newhead = pcur;newtail = pcur;}//如果鏈表不為空，就將新節(jié)點(diǎn)放到鏈表尾,else{newtail->next = pcur;newtail = pcur;}}//pcur指向的節(jié)點(diǎn)是不是val都要往下走pcur = pcur->next;}//因?yàn)橛锌赡芊祷氐氖强真湵?#xff0c;所以不能粗暴的去訪問(wèn)newtail->next//要先判斷要返回的newtail是否為空，也就是說(shuō)是否是空鏈表if (newtail){newtail->next = NULL;}return newhead;
}

2. 鏈表的中間結(jié)點(diǎn)

????????OJ鏈接：力扣（LeetCode）官網(wǎng) - 全球極客摯愛(ài)的技術(shù)成長(zhǎng)平臺(tái)

????????本題是說(shuō)，給出一個(gè)鏈表的頭節(jié)點(diǎn)head，然后找到這個(gè)鏈表的中間節(jié)點(diǎn)，如果有兩個(gè)中間節(jié)點(diǎn)，就返回第二個(gè)中間節(jié)點(diǎn)

思路1：

????????遍歷整個(gè)鏈表，數(shù)出一共有幾個(gè)節(jié)點(diǎn)，然后通過(guò)除2找到中間節(jié)點(diǎn)的"下標(biāo)"，然后通過(guò)"下標(biāo)"，再訪問(wèn)出中間節(jié)點(diǎn)的地址

????????很明顯，這個(gè)方法很麻煩

思路2：快慢指針?lè)?/h3>

????????跟前面雙指針那節(jié)一樣，這個(gè)快慢指針也不是真正的創(chuàng)造兩個(gè)指針，而是創(chuàng)造兩個(gè)具有類(lèi)似指針功能的變量

????????思路就是創(chuàng)造一個(gè)慢指針slow，一個(gè)快指針fast，然后slow走一步，fast走兩步，這樣fast走完的時(shí)候slow剛好來(lái)到鏈表中間

????????快慢指針?lè)ň褪峭ㄟ^(guò)只遍歷一次就能達(dá)到對(duì)整體進(jìn)行類(lèi)似除法運(yùn)算的功效，比如slow走1步fast走4步，fast走完，slow就走到整體的四分之一處

? ? ? ? 回到本題，在判斷結(jié)束掃描的條件時(shí)要注意，先判斷fast是否為NULL，利用短路的特性避免判斷fast->next，因?yàn)槿绻鹒ast為假了，去訪問(wèn)next的時(shí)候就會(huì)崩

struct ListNode* middleNode(struct ListNode* head) 
{struct ListNode* slow = head;struct ListNode* fast = head;//有一個(gè)為假就跳出循環(huán)while (fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}

3. 反轉(zhuǎn)鏈表

????????OJ鏈接：力扣（LeetCode）官網(wǎng) - 全球極客摯愛(ài)的技術(shù)成長(zhǎng)平臺(tái)

????????本體是說(shuō)給一個(gè)單鏈表的頭節(jié)點(diǎn)地址head，讓反轉(zhuǎn)鏈表，再將新鏈表的頭返回，值得注意的是這個(gè)鏈表可能是個(gè)空鏈表

思路1：

????????和第一題類(lèi)似，創(chuàng)建一個(gè)"新鏈表"，每次將舊鏈表的第一個(gè)節(jié)點(diǎn)拿下來(lái)，頭插到新鏈表

????????因?yàn)檫@題給的是單鏈表，不能用后面的節(jié)點(diǎn)訪問(wèn)前面的節(jié)點(diǎn)，所以不要想從最后一個(gè)節(jié)點(diǎn)開(kāi)始改變鏈接方向，因?yàn)楸闅v到最后一個(gè)節(jié)點(diǎn)就找不到前面的節(jié)點(diǎn)了

思路2：

????????用3個(gè)指針n1、n2、n3，初始狀態(tài)n1指向空，n2指向頭節(jié)點(diǎn)，n3指向第二個(gè)節(jié)點(diǎn)。然后將n2節(jié)點(diǎn)的指向變成n1，然后把n1變到n2的位置，n2變到n3的位置，再把n3滑到下一個(gè)節(jié)點(diǎn)。然后在n2不為空的情況下一直循環(huán)這個(gè)操作。

struct ListNode* reverseList(struct ListNode* head) 
{//如果傳過(guò)來(lái)的是空鏈表if (head == NULL){return head;}struct ListNode* n1 = NULL;struct ListNode* n2 = head;struct ListNode* n3 = head->next;while (n2){n2->next = n1;n1 = n2;n3 = n2;//如果n3已經(jīng)指向NULL了就不用往下滑了if (n3){n3 = n3->next;}        }return n1;
}

4. 合并兩個(gè)有序鏈表

????????OJ鏈接：力扣（LeetCode）官網(wǎng) - 全球極客摯愛(ài)的技術(shù)成長(zhǎng)平臺(tái)

????????本題是說(shuō)，給兩個(gè)升序鏈表的頭節(jié)點(diǎn)地址list1和list2，然后將兩個(gè)鏈表合并成一共新的升序鏈表，并返回新鏈表的頭，值得注意的是給出的兩個(gè)鏈表可能有空的

思路：

????????創(chuàng)建一個(gè)"新鏈表"，再用順序表中講到的那道合并數(shù)組的題的思想

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{//如果給出的某個(gè)鏈表為空，就返回另一個(gè)鏈表if (list1 == NULL){return list2;}if (list2 == NULL){return list1;}//兩個(gè)掃描原鏈表的指針struct ListNode* p1 = list1;struct ListNode* p2 = list2;//兩個(gè)控制新鏈表的指針struct ListNode* newhead = NULL;struct ListNode* newtail = NULL;//p1或p2有一個(gè)掃描完就退出循環(huán)while (p1 && p2){//如果p1掃到的數(shù)據(jù)更小if (p1->val < p2->val){//如果新鏈表中沒(méi)有節(jié)點(diǎn)if (newhead == NULL){newhead = p1;newtail = p1;}//如果新鏈表不為空else{newtail->next = p1;newtail = p1;}p1 = p1->next;}//如果p2掃到的數(shù)據(jù)更小else{//如果新鏈表為空if (newhead == NULL){newhead = p2;newtail = p2;}//如果新鏈表不為空else{newtail->next = p2;newtail = p2;}p2 = p2->next;}}//處理舊鏈表沒(méi)挪完的那部分if (p1){newtail->next = p1;}if (p2){newtail->next = p2;}return newhead;
}

5.?分割鏈表(帶頭鏈表的優(yōu)勢(shì))

????????本題我會(huì)距離說(shuō)明帶頭鏈表比不帶頭鏈表好在哪里

????????OJ鏈接：https://leetcode.cn/problems/partition-list-lcci/description/

????????本題給出一個(gè)鏈表的頭節(jié)點(diǎn)地址，和一個(gè)特定的值x，要求是把所存數(shù)據(jù)小于x的節(jié)點(diǎn)堆在前面，把大于等于x的節(jié)點(diǎn)堆在后面，堆放的時(shí)候不需要保存節(jié)點(diǎn)原來(lái)相對(duì)位置的有關(guān)信息

思路1：

????????創(chuàng)建一個(gè)"新鏈表"把原鏈表中小于x的節(jié)點(diǎn)頭插，把大于等于x的節(jié)點(diǎn)尾插

思路2：帶頭鏈表的優(yōu)點(diǎn)

????????先說(shuō)解題思路，我們創(chuàng)造兩個(gè)"新鏈表"，lesshead尾插小于x的節(jié)點(diǎn)，bighead尾插大于等于x的節(jié)點(diǎn)，最后把bighead連到lesshead后面

????????現(xiàn)在我們回憶一下，之前的代碼再每次插入新節(jié)點(diǎn)的時(shí)候都要判斷一下鏈表是否為空，這很麻煩。所以我們直接讓鏈表帶頭，這樣每次插入新節(jié)點(diǎn)的時(shí)候就不用判斷了，因?yàn)殒湵硪欢ú粸榭?#xff0c;它有一個(gè)不存儲(chǔ)數(shù)據(jù)的頭或者說(shuō)"哨兵位"，省去了插入時(shí)的很多麻煩

struct ListNode* partition(struct ListNode* head, int x) 
{//判斷傳過(guò)來(lái)的是否時(shí)空鏈表if (head == NULL){return head;}//創(chuàng)建兩個(gè)帶頭新鏈表struct ListNode* lesshead, * lesstail;struct ListNode* bighead, * bigtail;//申請(qǐng)頭節(jié)點(diǎn)空間，并將其地址記錄lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));bighead = bigtail = (struct ListNode*)malloc(sizeof(struct ListNode));//用pcur遍歷原鏈表，將節(jié)點(diǎn)放到對(duì)應(yīng)的新鏈表中struct ListNode* pcur = head;while (pcur){if (pcur->val < x){lesstail->next = pcur;lesstail = lesstail->next;}else{bigtail->next = pcur;bigtail = bigtail->next;}pcur = pcur->next;}//鏈接兩個(gè)鏈表//先將大鏈表的尾置空bigtail->next = NULL;//再接上，注意要掠過(guò)大鏈表的那個(gè)沒(méi)意義的頭lesstail->next = bighead->next;//先存上小鏈表的第一個(gè)存有效數(shù)據(jù)的節(jié)點(diǎn)struct ListNode* ret = lesshead->next;//在釋放兩個(gè)新鏈表的頭free(bighead);free(lesshead);return ret;
}

6.?環(huán)形鏈表的約瑟夫問(wèn)題

????????OJ鏈接：環(huán)形鏈表的約瑟夫問(wèn)題_?？皖}霸_?？途W(wǎng)

????????本題······哎呀這題我就不復(fù)述了，人家題干說(shuō)的挺清楚的

思路：循環(huán)鏈表

????????創(chuàng)建不帶頭單向循環(huán)鏈表，模擬圍成一圈的人，逢m就刪除節(jié)點(diǎn)

#include<stdlib.h>
//創(chuàng)建新節(jié)點(diǎn)
struct ListNode* BuyNode(int x)
{struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));newnode->val = x;newnode->next = NULL;return newnode;
}
//創(chuàng)建鏈表
struct ListNode* creatlist(int n)
{//先創(chuàng)建一個(gè)頭節(jié)點(diǎn)struct ListNode* phead = BuyNode(1);struct ListNode* ptail = phead;//再循環(huán)進(jìn)行尾插，形成鏈表for (int i = 2; i <= n; i++){ptail->next = BuyNode(i);ptail = ptail->next;}//讓鏈表首尾相連ptail->next = phead;return phead;
}int ysf(int n, int m) 
{//創(chuàng)建不帶頭單向循環(huán)鏈表struct ListNode* phead = creatlist(n);struct ListNode* pcur = phead;struct ListNode* prev = NULL;//逢m刪除節(jié)點(diǎn),直到剩下最后一個(gè)節(jié)點(diǎn)int count = 1;while (pcur->next != pcur){if (m == count){//刪除當(dāng)前節(jié)點(diǎn)prev->next = pcur->next;free(pcur);count = 1;pcur = prev->next;}else{//pcur往后走prev = pcur;pcur = pcur->next;count++;}}return pcur->val;
}

? ? ? ? 不必?fù)?dān)心當(dāng) m==1 的使得 prev->next 非法的情況，while的循環(huán)條件就已經(jīng)把這種情況擋在外面了，而且題干里說(shuō)了一定會(huì)剩下來(lái)一個(gè)人，所以返回pcur的數(shù)據(jù)也是沒(méi)有問(wèn)題的。