?👀樊梓慕：個人主頁

?🎥個人專欄：《C語言》《數(shù)據(jù)結(jié)構(gòu)》《藍(lán)橋杯試題》《LeetCode刷題筆記》

🌝每一個不曾起舞的日子，都是對生命的辜負(fù)。

目錄

前言：

【LeetCode】203.移除鏈表元素

【LeetCode】206.反轉(zhuǎn)鏈表

?思路一

思路二

【LeetCode】876.鏈表的中間結(jié)點

快慢指針法

【LeetCode】劍指Offer 22.鏈表中倒數(shù)第k個結(jié)點

快慢指針法?

【LeetCode】21.合并兩個有序鏈表

【LeetCode】劍指Offer Ⅱ 27.回文鏈表

前言：

本系列博文博主會講解鏈表的經(jīng)典OJ題目。

歡迎大家📂收藏📂以便未來做題時可以快速找到思路，巧妙的方法可以事半功倍。

=========================================================================

GITEE相關(guān)代碼：🌟fanfei_c的倉庫🌟

=========================================================================

【LeetCode】203.移除鏈表元素

原題鏈接：🍏移除鏈表元素🍏

題目：給你一個鏈表的頭節(jié)點?head?和一個整數(shù)?val?，請你刪除鏈表中所有滿足?Node.val == val?的節(jié)點，并返回?新的頭節(jié)點?。

?要想刪除當(dāng)前元素，需要知道當(dāng)前元素的位置，及前一個元素的位置，并且保存下一個元素的位置。

所以我們需要三個指針：

• 一個指針命名為cur，作用是遍歷；
• 一個指針命名為prev，指向位置為cur的前一個位置，作用是刪除（prev->next=cur->next）；
• 一個next指針用來保存cur的后一個位置，確保free掉cur后仍然可以找到下一元素。

代碼實現(xiàn)：?

/*
解題思路：從頭節(jié)點開始進(jìn)行元素刪除，每刪除一個元素，需要重新鏈接節(jié)點
*/
struct ListNode* removeElements(struct ListNode* head, int val) {if(head == NULL)return NULL;struct ListNode* cur = head;struct ListNode* prev = NULL;while(cur){//如果當(dāng)前節(jié)點是需要刪除的節(jié)點if(cur->val == val){//首先保存下一個節(jié)點struct ListNode* next = cur->next;//如果刪除的為頭節(jié)點，更新頭節(jié)點//否則讓當(dāng)前節(jié)點的前趨節(jié)點鏈接next節(jié)點if(prev == NULL){head = cur->next;}else{prev->next = cur->next;  }//釋放當(dāng)前節(jié)點，讓cur指向nextfree(cur);cur = next;}else{//如果cur不是需要刪除的節(jié)點，則更新prev,curprev = cur;cur = cur->next;}}return head;
}

注意：考慮極端情況，如首個位置就是val的情況，作單獨處理。

【LeetCode】206.反轉(zhuǎn)鏈表

原題鏈接：🍏反轉(zhuǎn)鏈表🍏

題目：給你單鏈表的頭節(jié)點?head?，請你反轉(zhuǎn)鏈表，并返回反轉(zhuǎn)后的鏈表。

??

?思路一

同樣的我們需要三個指針來完成這一操作：

• 一個指針命名為cur，作用是遍歷；
• 一個指針命名為prev，作用是拿到cur的前一個地址，而后改變cur->next指向prev；
• 一個指針命名為next，作用是保存cur的后一個位置，防止修改cur->next后找不到cur的后一個位置。

代碼實現(xiàn)：

struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* prev = NULL;struct ListNode* cur = head, * next = head;if (cur)// 檢查cur是否為空{(diào)next = cur->next;}while (cur){// 往后走prev = cur;cur = next;if(next)// 檢查next是否為空next = next->next;}return prev;
}

思路二

取結(jié)點頭插，完成逆置。

大家只要掌握了頭插就很簡單了。

代碼實現(xiàn)：

// 取節(jié)點頭插的思想完成逆置
struct ListNode* reverseList(struct ListNode* head) {struct ListNode* newhead = NULL;struct ListNode* cur = head;while(cur){struct ListNode* next = cur->next;//頭插新節(jié)點，更新頭cur->next = newhead;newhead = cur;cur = next;}return newhead;
}

【LeetCode】876.鏈表的中間結(jié)點

原題鏈接：🍏鏈表的中間結(jié)點🍏

題目：給你單鏈表的頭結(jié)點?head?，請你找出并返回鏈表的中間結(jié)點。

如果有兩個中間結(jié)點，則返回第二個中間結(jié)點。

快慢指針法

若想找到中間結(jié)點，我們可以定義兩個指針：

• 一個命名為slow，令slow每次走一步；
• 一個命名為fast，令fast每次走兩步。

這樣當(dāng)fast為NULL，或fast->next為NULL時，slow恰好處于中間位置，最后返回slow即可。

代碼實現(xiàn)：

struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slow=head;struct ListNode* fast=head;while(fast && fast->next)// 分別為奇數(shù)個與偶數(shù)個的判斷條件{slow=slow->next;fast=fast->next->next;}return slow;
}

【LeetCode】劍指Offer 22.鏈表中倒數(shù)第k個結(jié)點

原題鏈接：🍏鏈表中倒數(shù)第k個結(jié)點🍏

題目：輸入一個鏈表，輸出該鏈表中倒數(shù)第k個節(jié)點。

快慢指針法?

同樣需要快慢指針的方法。

令fast先走k步，slow不動，然后slow與fast同時向后走，直到fast為NULL，此時slow的位置就是倒數(shù)第k個位置。

代碼實現(xiàn)：

struct ListNode* getKthFromEnd(struct ListNode* head, int k)
{struct ListNode* slow=head,* fast=head;while(k--){if(fast==NULL){return NULL;}   fast=fast->next;}while(fast){slow=slow->next;fast=fast->next;}return slow;
}

【LeetCode】21.合并兩個有序鏈表

原題鏈接：🍏合并兩個有序鏈表🍏

題目：將兩個升序鏈表合并為一個新的?升序?鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的。

?思路：取小的尾插。

?注意：極端情況的判斷，如其中一個鏈表為空等等。

代碼實現(xiàn)：?

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{if(list1==NULL)// 判斷其中一個鏈表為空的情況{return list2;}if(list2==NULL)// 判斷其中一個鏈表為空的情況{return list1;}struct ListNode* head=NULL,*tail=NULL;while(list1 && list2){if(list1->val<list2->val){if(head==NULL)// 頭結(jié)點直接賦值{head=tail=list1;}else// 尾插{tail->next=list1;tail=tail->next;}list1=list1->next;}else{if(head==NULL)// 頭結(jié)點直接賦值{head=tail=list2;}else// 尾插{tail->next=list2;tail=tail->next;}list2=list2->next;}}if(list1)// list1有剩余{tail->next=list1;}if(list2)// list2有剩余{tail->next=list2;}return head;
}

【LeetCode】劍指Offer Ⅱ 27.回文鏈表

原題鏈接：🍏回文鏈表🍏

題目：給定一個鏈表的?頭節(jié)點?head?，請判斷其是否為回文鏈表。

如果一個鏈表是回文，那么鏈表節(jié)點序列從前往后看和從后往前看是相同的。

?思路：找到中間結(jié)點，將后半部分逆置，最后令前后兩部分一一對比，如果結(jié)點的值全部相同，則為回文。

?剛好我們可以利用上面實現(xiàn)過的函數(shù)：鏈表的中間結(jié)點和反轉(zhuǎn)鏈表。

代碼實現(xiàn)：

// 找到中間結(jié)點
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slow = head;struct ListNode* fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}// 反轉(zhuǎn)一個單鏈表
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* tail = NULL;struct ListNode* cur = head, * next = head;while (next){next = cur->next;cur->next = tail;tail = cur;cur = next;}return tail;
}// 判斷回文結(jié)構(gòu)
bool isPalindrome(struct ListNode* head)
{struct ListNode* mid=middleNode(head);struct ListNode* newhead=reverseList(mid);while(head && newhead){if(head->val!=newhead->val){return false;}else{head=head->next;newhead=newhead->next;}}return true;
}

?=========================================================================

如果你對該系列文章有興趣的話，歡迎持續(xù)關(guān)注博主動態(tài)，博主會持續(xù)輸出優(yōu)質(zhì)內(nèi)容

🍎博主很需要大家的支持，你的支持是我創(chuàng)作的不竭動力🍎

🌟~?點贊收藏＋關(guān)注 ~🌟

=========================================================================?