線性表之鏈表OJ（上）

“海鷗不再眷戀大海，可以飛更遠” ——《明明就》

Hello，我們又見面啦！！！😊

筆者作為一個剛剛入門的小白，鏈表還是一個前期頗有挑戰性的專題。

所以關于鏈表OJ題，我打算分三篇博客進行一個分享，上下兩篇以及后續一個環形鏈表的專題。

（上）：主要是一些鏈表的基本操作，難度一般。

（下）：相較于（上），鏈表帶上了一些性質，難度會提高。

環形鏈表專題：主要是認識一下環形鏈表，學習一下環形鏈表的操作，涉及一些證明，難度在三篇中是最高的。

博主建議：先不要看題解，自己把題目做一遍。這樣效果更好哦

**GO！GO！GO！讓我們進入正題！**😉

---

1. 移除鏈表元素

題目鏈接：203. 移除鏈表元素(leetcode)

**題目描述：**給你一個鏈表的頭節點 head 和一個整數 val ，請你刪除鏈表中所有滿足 Node.val == val 的節點，并返回 新的頭節點 。

圖示：

題解代碼：

typedef struct ListNode Node; struct ListNode* removeElements(struct ListNode* head, int val) {Node *prev=NULL,*cur=head,*next;while(cur){next = cur->next;if(cur->val==val){if(!prev)head=head->next;elseprev->next=cur->next;free(cur);}elseprev=cur;cur=next;}return head; }

注意我們沒有用哨兵節點，所以在刪除時，需要注意頭刪的邏輯

2. 反轉鏈表

題目鏈接：206. 反轉鏈表leetcode

**題目描述：**給你單鏈表的頭節點 head ，請你反轉鏈表，并返回反轉后的鏈表。

圖示：

需要注意的是，我們此處翻轉鏈表是對于原鏈表的節點進行操作，諸如遍歷鏈表把數據放在數組中，逆序再建一個鏈表的方法均不符合題意。

2.1 循環迭代的寫法

typedef struct ListNode Node; struct ListNode* reverseList(struct ListNode* head) {Node *prev=NULL,*cur=head,*next;while(cur){next=cur->next;cur->next=prev;prev=cur;cur=next;}return prev; }

注意line 7 - 10 的順序，也就是反轉的邏輯！

2.2 遞歸的寫法

ListNode* reverse(ListNode *prev,ListNode* cur) {if(cur==NULL) return prev; //遞歸出口ListNode *temp=cur->next;cur->next=prev;return reverse(cur,temp); }ListNode* reverseList(ListNode* head){return reverse(NULL,head);} };

3. 找鏈表的中間節點

題目鏈接：876. 鏈表的中間結點

**題目描述：**給定一個頭結點為 head 的非空單鏈表，返回鏈表的中間結點。

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

這道題我們來初始一下==快慢指針==法：

快慢指針都指向頭節點

每次循環迭代，慢指針走一步，快指針走兩步

其實直觀上很容易理解，快指針的“速度”為慢指針的兩倍，當快指針走到頭時，慢指針正好走到一半的位置。

結合圖像我們來理解一下：

代碼實現：

typedef struct ListNode Node; struct ListNode* middleNode(struct ListNode* head) {Node *fast,*slow;fast=slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;}return slow; }

**思考題：循環條件能不能寫成fast->next&&fast？為什么？**🤔

4.鏈表中倒數第k個節點

題目鏈接：[鏈表中倒數第k個結點](鏈表中倒數第k個結點_牛客題霸_牛客網 (nowcoder.com))

**題目描述：**輸入一個鏈表，輸出該鏈表中倒數第k個結點。如果k>鏈表長度，返回NULL

這道題其實和上題比較類似，主要我們不知道鏈表長度，無法確定倒數第k到底在哪。

這邊我們也是用==快慢指針==解決:

快慢指針都指向頭節點

讓快指針先走k步

讓快慢指針一起往前走，直至快指針走到頭

快指針始終領先慢指針k步，當快指針走到尾時，慢指針即為倒數第k個節點

代碼實現：

typedef struct ListNode Node; struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {Node *fast,*slow;fast=slow=pListHead;while(k--){if(!fast) return NULL;fast=fast->next;}while(fast){fast=fast->next;slow=slow->next;}return slow; }

5.合并兩個有序鏈表

題目鏈接：21. 合并兩個有序鏈表

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

圖示：

思路類似歸并兩個有序數組，注意這邊要對原來的節點進行操作

這邊建議運用哨兵節點來簡化我們放入節點的邏輯

typedef struct ListNode Node; struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {Node* head=(Node*)malloc(sizeof(Node)),*tail=head;//head->next=list1->val<list2->val?list1:list2;while(list1&&list2){if(list1->val<list2->val){tail->next=list1;tail=list1;list1=list1->next;}else{tail->next=list2;tail=list2;list2=list2->next;}}if(!list1) tail->next=list2;if(!list2) tail->next=list1;Node* rethead=head->next;free(head);return rethead; }

！！與歸并數組時不同的是，while循環后兩個鏈表必定是一個表的節點全部放入了歸并后的鏈表，另一個表的節點還未全部放入到歸并后的鏈表。

故while循環后需要再把這些節點放入，這時我們就不需要一個節點一個節點放入，直接把list連到tail后面即可(后續節點都連在一起啦)

注意哪個空就要連另一個哦

---

🤗到此我們這博客也接近尾聲啦。

😊怎么樣感覺難度是不是還好，這篇還只是開胃菜，下期難度up，up🤩

😊希望大家能在閱讀完后有所收獲！！！這將是對我最大的激勵！

敲代碼，碼字，作圖不易，期待一個小小的點贊??

如果你對博客內容有什么疑惑，或者對思考題有什么不解，很歡迎大家來和我交流討論哦?

本期所有的代碼我將傳到我的gitee倉庫中，如有需要可自行下載

倉庫傳送門：數據結構

我們下篇博客見！😘

總結

以上是生活随笔為你收集整理的【绝知此事要躬行】线性表之链表OJ(上)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。