目錄

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

題目

?思路

?代碼

206.反轉(zhuǎn)鏈表

題目

思路

代碼

21.合并兩個有序鏈表

題目

思路

代碼

203.移除鏈表元素

題目

思路

?代碼

---

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

876. 鏈表的中間結(jié)點 - 力扣（LeetCode）https://leetcode.cn/problems/middle-of-the-linked-list/description/

題目

給你單鏈表的頭結(jié)點?head?，請你找出并返回鏈表的中間結(jié)點。如果有兩個中間結(jié)點，則返回第二個中間結(jié)點。

示例：

?思路

快慢指針法：在單鏈表頭節(jié)點head位置創(chuàng)建兩個指針fast和slow，兩個指針通過while循環(huán)依次向后遍歷，slow一次跨越一個節(jié)點slow->next，fast一次跨越兩個節(jié)點fast->next->next,當(dāng)fast或fast的下一節(jié)點fast->next為空時，終止循環(huán)，則此時的slow所在節(jié)點為中間節(jié)點。

?

?代碼

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

206.反轉(zhuǎn)鏈表

206. 反轉(zhuǎn)鏈表 - 力扣（LeetCode）https://leetcode.cn/problems/reverse-linked-list/description/

題目

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

示例：?

思路

依次斷開原鏈表的第一個節(jié)點，用頭插的方式插入新鏈表，注意注意要保存好cur的下一節(jié)點next。

代碼

struct ListNode* reverseList(struct ListNode* head){struct ListNode* cur=head;struct ListNode* newhead=NULL;while(cur){//保存下一節(jié)點struct ListNode* next=cur->next;//頭插cur->next=newhead;newhead=cur;cur=next;}return newhead;
}

21.合并兩個有序鏈表

21. 合并兩個有序鏈表 - 力扣（LeetCode）https://leetcode.cn/problems/merge-two-sorted-lists/description/

題目

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

示例：

思路

創(chuàng)建一個新的結(jié)構(gòu)體指針head作為合成的新鏈表，

創(chuàng)建兩個指針，指向兩個鏈表，將兩個有序鏈表從頭節(jié)點開始，依次進行比較，取較小的尾插到新的鏈表，通過while循環(huán)直到其中一個鏈表為空，不為空的鏈表直接尾插到新鏈表即可。

?圖示如下👇

在插入第一個節(jié)點前，我們也可以選擇放一個哨兵位在頭節(jié)點前面（哨兵位不算鏈表節(jié)點），這樣就減少了第一次尾插時對tail是否為空的判斷，代碼更加簡潔。

代碼

不帶哨兵位

帶哨兵位

203.移除鏈表元素

203. 移除鏈表元素 - 力扣（LeetCode）https://leetcode.cn/problems/remove-linked-list-elements/description/

題目

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

示例：

思路

?這道題可以用雙指針法，兩個指針逐漸向后遍歷，當(dāng)遇到滿足cur->val=val的節(jié)點時，（滿足cur==hand時用頭刪的方法）cur到下一節(jié)點保存下一節(jié)點，同時刪除滿足條件的節(jié)點，每趟循環(huán)cur會賦給prev，cur再到下一節(jié)點，當(dāng)cur遍歷鏈表完為NULL的時候，prev剛好在最后一個節(jié)點，prev->next為鏈表結(jié)尾賦NULL。

?代碼

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