?🔥個人主頁：@草莓熊Lotso

🎬作者簡介：C++研發方向學習者

📖個人專欄：?《C語言》?《數據結構與算法》《C語言刷題集》《Leetcode刷題指南》

??人生格言：生活是默默的堅持，毅力是永久的享受。

前言：隨著編程相關知識點的學習，我們LeetCode的刷題也不能落下。在前面我們也接觸到了洛谷和牛客這兩個刷題網站，但是博主一直都在推薦大家使用力扣，是因為力扣的判題嚴謹且大部分都是接口型題目，與面試中的筆試題也更加貼合。那么還是老樣子，博主會為大家提供我自己的思路和代碼，但是算法題的解法肯定不止一個，歡迎大家一起交流和討論。

---

目錄

1.反轉鏈表?

2.鏈表的中間結點

3.合并兩個有序鏈表

---

1.反轉鏈表?

題目鏈接：206. 反轉鏈表 - 力扣（LeetCode）

題目描述：?

題目示例：?

?思路：?迭代法實現鏈表的反轉

解題過程：

1.cur指向鏈表頭結點，newhead初始化為空(用于存儲反轉后的新鏈表)

2.每次迭代中，先將cur的下一個節點next保存下來，不然后面就找不到了，然后將cur->next指向當前新鏈表newhead 接著讓newhead來到cur的位置，再把cur移動到保存的next結點

3.循環結束后，newhead即為反轉后的鏈表頭結點

具體解題過程圖示如下：

復雜度：?

• 時間復雜度: O(n)

• 空間復雜度: O(1)

代碼演示：?

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* reverseList(struct ListNode* head) {struct ListNode*cur=head;struct ListNode*newhead=NULL;while(cur){struct ListNode* next=cur->next;cur->next=newhead;newhead=cur;cur=next;}return newhead;
}

2.鏈表的中間結點

題目鏈接：876. 鏈表的中間結點 - 力扣（LeetCode）

題目描述：?

題目示例：?

思路：?利用快慢指針求解

解題過程：

1.定義兩個指針，一個slow慢指針，一個fast快指針，慢指針每次走一步，快指針每次走兩步，剛開始都在頭結點。

2.分兩種情況討論，當結點個數為奇數時我們可以發現fast->next為NULL時slow指針剛好走到中間結點，當結點個數為偶數時我們可以發現fast為NULL時slow指針剛好走到中間結點。

3.我們以兩種不同的情況為結束條件，進行循環，當循環結束時，slow結點的位置就是中間結點的位置，返回slow就可以了

具體解題過程圖示如下：

復雜度：?

• 時間復雜度: O(n)

• 空間復雜度: O(1)

代碼演示：?

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* middleNode(struct ListNode* head) {struct ListNode*slow=head;struct ListNode*fast=head;while(fast!=NULL&&fast->next!=NULL){slow=slow->next;fast=fast->next->next;}return slow;
}

---

3.合并兩個有序鏈表

題目描述：21. 合并兩個有序鏈表 - 力扣（LeetCode）

題目描述：?

題目示例：?

思路：?創建新鏈表，遍歷并比較原鏈表中節點的值，小的尾插到新鏈表中

解題過程：

1.如果list1或者list2中有一個為空的話，返回非空的那個

2.定義一個哨兵位的頭結點和一個尾節點，申請空間；這樣可以省掉后續尾插時的空節點特殊處理 3.遍歷鏈表，注意條件，一定是兩個都不能為空，然后比較大小，小的尾插到尾節點后。尾節點向前走，如果是l1的小，l1也要向前走，l2同理；

4.如果其中一個先結束，那么直接把剩下的一個鏈表尾插到newtail后面就行，不用循環；

5.我們最后需要返回的不是head而是head->next,定義一個新節點newhead記錄下來。然后釋放掉head，并置空

6.返回newhead就可以了

具體解題過程圖示如下：?

復雜度：

• 時間復雜度: O(1)

• 空間復雜度: O(n)

代碼演示：?

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if(list1==NULL)return list2;if(list2==NULL)return list1;struct ListNode* head=NULL;struct ListNode* tail=NULL;head=tail=(struct ListNode*)malloc(sizeof(struct ListNode));while(list1!=NULL&&list2!=NULL){if(list1->val<list2->val){tail->next=list1;list1=list1->next;}else{tail->next=list2;list2=list2->next;}tail=tail->next;}if(list1!=NULL){tail->next=list1;}if (list2!=NULL){tail->next=list2;}struct ListNode*newhead=head->next;free(head);return newhead;
}

---

往期回顧：

【LeetCode刷題指南】--數組串聯，合并兩個有序數組，刪除有序數組中的重復項

【LeetCode刷題指南特別篇】--移除鏈表元素，調試技巧，鏈表分割

結語：本篇文章就到此結束了，《LetetCode刷題指南》中的題目比起之間的C語言刷題集中的題目，肯定會更加復雜一些。而且題目形式也不一樣，大家需要注意一下。如果文章對你有幫助的話，歡迎評論，點贊，收藏加關注，感謝大家的支持