🔥博客主頁：小王又困了

📚系列專欄：數據結構

🌟人之為學，不日近則日退?

??感謝大家點贊👍收藏?評論??

---

目錄

一、鏈表分割

💡方法一：

二、鏈表的回文

💡方法一：?

三、相交鏈表

💡方法一：?

四、環形鏈表

?💡方法一：?

---

🗒?前言：

在上一期中我們給大家介紹了單鏈表，也了解了單鏈表的實現。接下來就讓我們進入實踐，練習一些經典題目，讓我們對單鏈表的理解更加深入

一、鏈表分割

題目：

💡方法一：

我們創建兩條鏈表，把小于x的節點放在一條鏈表中，剩余的放在另一條節點，最后將兩條鏈表連接起來。在這里要使用帶哨兵位的鏈表，不用考慮頭插和第一條鏈表為空的問題，可以大大減少代碼量。

?注意：要將鏈表最后一個節點的指針域置為空，不然會導致鏈表循環。

ListNode* partition(ListNode* pHead, int x) 
{struct ListNode* lhead ,*ltail,*ghead,*gtail;ghead=gtail=(struct ListNode*)malloc(sizeof(struct ListNode));lhead=ltail=(struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur=pHead;while(cur){if(cur->val<x){ltail->next=cur;ltail=ltail->next;}else  {gtail->next=cur;gtail=gtail->next;}cur=cur->next；}ltail->next=ghead->next;gtail->next=NULL;struct ListNode* head=lhead->next;free(ghead);free(lhead);return head;
}

二、鏈表的回文

題目：

💡方法一：?

我們先找到中間節點，然后將后面的節點反轉，分別從頭節點和中間節點開始比較，如果兩兩節點的數據域有一對不相等，返回flase；如果都相等返回true。

class PalindromeList {public://找中間節點struct ListNode* middleNode(struct ListNode* head) {struct ListNode* fast = head;struct ListNode* slow = head;while (fast && fast->next) {fast = fast->next->next;slow = slow->next;}return slow;}//反轉鏈表struct ListNode* reverseList(struct ListNode* head) {struct ListNode* cur = head;struct ListNode* newnode = NULL;while (cur) {//保存節點struct ListNode* next = cur->next;//頭插cur->next = newnode;newnode = cur;cur = next;}return newnode;}bool chkPalindrome(ListNode* head) {   struct ListNode* mid=middleNode(head);struct ListNode* rmid=reverseList(mid);struct ListNode* cur=head;while(rmid&&cur){if(rmid->val!=cur->val){return false;}else {rmid=rmid->next;cur=cur->next;}}return true;}
};

三、相交鏈表

題目：

💡方法一：?

在做這道題，我們可以分為兩步：

1.判斷是否相交：

? ? ? ? 遍歷兩條鏈表，比較最后一個節點的地址，地址相等，說明兩條鏈表相交。

2.找起始節點：

? ? ? ? 先計算出兩條鏈表的長度，計算出它們的差值，讓長的鏈表先走差距步，然后兩條鏈表一起走，相等時返回的就是相交的起始節點。

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{struct ListNode* curA=headA,*curB=headB;int lenA=1,lenB=1;while(curA->next){curA=curA->next;lenA++;}while(curB->next){curB=curB->next;lenB++;}if(curA->next!=curB->next){return NULL;}//求兩鏈表的差距int gap=abs(lenA-lenB);struct ListNode* longlist=headA,*shortlist=headB;if(lenA<lenB){longlist=headB;shortlist=headA;}//長鏈表先走差距步while(gap--){longlist=longlist->next;}while(longlist!=shortlist){longlist=longlist->next;shortlist=shortlist->next;}return longlist;
}

四、環形鏈表

題目：

?💡方法一：?

?當我們定義快慢指針，快指針一次走兩步，慢指針一次走一步。如果鏈表存在環，在進入環中快指針一定可以追上慢指針。因為每走一步距離就減1，當減到0時就追上了。

• 假設起點到入口點距離為L
• 假設環的周長為C
• 假設入口點到相遇點的距離為X

我們通過快慢指針走過的路程來判斷，但在這里要注意環的周長很小時，所以在這里要考慮兩種情況：?

情況一：slow進環后一圈之內，fast一定追上slow

• slow走的距離：L+X
• fast走的距離：L+C+X

情況二：slow進環時，fast已經走了n圈

• slow走的距離：L+X
• fast走的距離：L+nC+X?

由于快指針速度使慢指針的二倍，所以快指針走的路程也是慢指針的二倍。由此可得出：

結論：慢指針從起點開始走，快指針從相遇點開始走，它們最終會相遇在入口點。

struct ListNode *detectCycle(struct ListNode *head) 
{struct ListNode* slow,* fast;slow=fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(fast==slow){struct ListNode* meet=fast;while(head!=meet){meet=meet->next;head=head->next;}return meet;}}return NULL;
}

本次的內容到這里就結束啦。希望大家閱讀完可以有所收獲，同時也感謝各位讀者三連支持。文章有問題可以在評論區留言，博主一定認真認真修改，以后寫出更好的文章。你們的支持就是博主最大的動力。