線性表之鏈表OJ（下）

“我不唱聲嘶力竭的情歌，不表示沒有心碎的時刻”——《孤獨患者》

經過上期鏈表OJ（上）

相信大家也都摩拳擦掌準備迎接這期難度稍高的鏈表OJ下啦，沖沖沖！

---

1.鏈表分割（牛客）

題目鏈接 :CM11 鏈表分割

題目描述：

現有一鏈表的頭指針1ListNode* pHead，給一定值x，編寫一段代碼將所有小于x的結點排在其余結點之前，且不能改變原來的數據順序，返回重新排列后的鏈表的頭指針。

思路：類似于上期合并兩個有序鏈表的思路，這次我們要用兩個鏈表，為了簡化我們的邏輯，使用帶哨兵的鏈表。

1. 遍歷原鏈表，一個存放值小于x的節點，另一個存值大于等于x的節點。
2. 將兩個鏈表連接起來
3. 記錄要返回的頭，釋放哨兵

圖示：

代碼實現：

class Partition { public:ListNode* partition(ListNode* pHead, int x) {ListNode* LessHead=new ListNode(0);ListNode* GreaterHead=new ListNode(0);ListNode *LessTail=LessHead, *GreaterTail=GreaterHead;for(ListNode* cur=pHead;cur;cur=cur->next){if(cur->val<x){LessTail->next=cur;LessTail=cur;}else{GreaterTail->next=cur;GreaterTail=cur;}}LessTail->next=GreaterHead->next;GreaterTail->next=NULL;ListNode* head=LessHead->next;delete LessHead;delete GreaterHead;return head;} };

---

2.鏈表的回文結構

題目鏈接：鏈表的回文結構

題目描述：

對于一個鏈表，請設計一個時間復雜度為O(n),額外空間復雜度為O(1)的算法，判斷其是否為回文結構。

給定一個鏈表的頭指針A，請返回一個bool值，代表其是否為回文結構。保證鏈表長度小于等于900。

我們遇到的困難主要是這是個單向的鏈表。沒法向前訪問節點，需要能“逆序”

思路一：

找中間節點(快慢指針，詳見OJ(上))

逆序中間節點之后的鏈表

判斷前后是否一樣

圖示：

代碼實現：

//返回一個鏈表的中間節點 //快慢節點 ListNode* middleNode(ListNode *head) {ListNode *slow,*fast;fast=slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;}return slow; } //逆置鏈表，返回新的頭節點 // 1.三個指針翻轉鏈表 ListNode* reverseList1(ListNode* head) {ListNode *prev=NULL,*cur=head;while(cur){ListNode* next=cur->next;cur->next=prev;prev=cur;cur=next;}return prev; } //2.頭插法翻轉鏈表 ListNode* reverseList2(ListNode* head) {ListNode* newHead=NULL;ListNode* cur=head;while(cur){ListNode *next=cur->next;cur->next=newHead;newHead=cur;cur=next;}return newHead; } class PalindromeList { public:bool chkPalindrome(ListNode* A) {//獲得中間節點ListNode* middle=middleNode(A);//將中間節點開始往后的鏈表逆置//ListNode* rHead=reverseList1(middle);ListNode* rHead=reverseList2(middle);while(A&&rHead){if(A->val==rHead->val){A=A->next;rHead=rHead->next;}elsereturn false;}return true;} };

！！！不推薦這種寫法！！！

因為這種寫法改變了傳入鏈表的結構，而我們這邊的需求只是判斷一個鏈表是否具有回文結構。

思路二(利用棧實現)：

1. 找中間節點
2. 把頭至中間節點（不包括）入棧
3. 從中間節點開始，棧頂元素->val和cur->val相等就出棧
4. 最后判斷棧是否為空

代碼實現：

class PalindromeList { public:bool chkPalindrome(ListNode* A){ListNode *fast,*slow,*middle,*cur;fast=slow=A;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;}middle=slow;stack<ListNode*> st;for(cur=A;cur!=middle;cur=cur->next)st.push(cur);for(cur=middle;cur;cur=cur->next){if(st.top()->val==cur->val)st.pop();}if(st.empty())return true;return false;} };

---

3.相交鏈表

題目鏈接：160. 相交鏈表

題目描述：

給你兩個單鏈表的頭節點 headA 和headB ，請你找出并返回兩個單鏈表相交的起始節點。如果兩個鏈表不存在相交節點，返回null 。

圖示兩個鏈表在節點c1 開始相交：

來源：力扣（LeetCode）

思路：

要判斷鏈表是否相交比較簡單，兩個鏈表都走到尾，看最后一個節點是否相同即可（因為鏈表相交一定是這種倒著的Y型，而不可能是X型）

我們還需要返回第一個相交節點，如果兩個鏈表長度相同，一起遍歷，如果節點相同直接返回即可。

在長度不同的情況下，長的先走gap步，再一起走即可

代碼實現：

class Solution { public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode *pa=headA,*pb=headB;int lenA=1,lenB=1;while(pa->next){lenA++;pa=pa->next;}while(pb->next){lenB++;pb=pb->next;}if(pa!=pb)return NULL;ListNode *shortList=headA,*longList=headB;if(lenA>lenB){shortList=headB;longList=headA;}int gap=abs(lenA-lenB);while(gap--)longList=longList->next;while(shortList&&longList){if(shortList==longList)return longList;longList=longList->next;shortList=shortList->next;}return NULL;} };

---

4.復制帶隨機指針的鏈表

題目鏈接：138. 復制帶隨機指針的鏈表

題目描述：

給你一個長度為 n的鏈表，每個節點包含一個額外增加的隨機指針 random ，該指針可以指向鏈表中的任何節點或空節點。

構造這個鏈表的 深拷貝。 深拷貝應該正好由 n個 全新 節點組成，其中每個新節點的值都設為其對應的原節點的值。新節點的 next 指針和 random指針也都應指向復制鏈表中的新節點，并使原鏈表和復制鏈表中的這些指針能夠表示相同的鏈表狀態。復制鏈表中的指針都不應指向原鏈表中的節點 。

例如，如果原鏈表中有 X 和Y 兩個節點，其中 X.random --> Y 。那么在復制鏈表中對應的兩個節點 x 和 y ，同樣有x.random --> y 。

返回復制鏈表的頭節點。

來源：力扣（LeetCode）

示意圖（源自力扣）：

這題是本blog中難度最高的一題，無論是從思路上還是代碼的控制上都有一定的挑戰性

首先我們要理解深拷貝

這是C++中和淺拷貝相對的一個概念。這邊我們不過多深入的討論（后續我會在C++專題中深入討論）

此處可以理解為，我們再內存中自己申請節點，再按照這個鏈表連接的樣子，來把這些節點連接起來

“如果原鏈表中有 X 和Y 兩個節點，其中 X.random --> Y 。那么在復制鏈表中對應的兩個節點 x 和 y ，同樣有x.random --> y ”

是一個**“照貓畫虎“**的過程。

分析：

如果不含random指針，這個過程是很簡單的。遍歷原鏈表，復制一個當前節點，按順序建立一個新表即可。

但有了random指針，問題就復雜起來了。

主要在于我們在原表中，通過random指針可以知道某個節點的random指針指向哪個節點，但是在建立新表的過程中，我們并找不到新表的random指針該指向哪個新表中的節點（即新表和原表節點之間并無聯系）

這個時候我們要解決這個問題，必須在原表與新表之間建立一種聯系

我們采取這樣一種做法：

把自己申請的拷貝節點連接在原節點的后面。

這樣通過random指針找到的原節點的后一個就是新表中對應拷貝節點的random指針指向的拷貝節點。

圖像解析：

解法：

1. 將拷貝節點連接到原節點后面
2. 處理拷貝節點的random指針
3. 將拷貝節點在原鏈表上”剪“下來并連接形成新表

代碼實現：

typedef struct Node Node; struct Node* copyRandomList(struct Node* head) {//1.將拷貝節點連接到原節點后面Node* cur=head;while(cur){Node* next=cur->next;Node* copy=(Node*)malloc(sizeof(Node));copy->val=cur->val;copy->next=next;cur->next=copy;cur=next;}//2.處理拷貝節點的random指針cur=head;while(cur){Node* copy=cur->next;if(!(cur->random))copy->random=NULL;elsecopy->random=cur->random->next;cur=copy->next;}//3.將拷貝節點剪下來并連接cur=head;Node *copyhead,*copytail;copyhead=copytail=NULL;while(cur){Node* copy=cur->next;if(copyhead==NULL)copyhead=copy;else copytail->next=copy;copytail=copy;cur=cur->next=copy->next;}return copyhead; }

---

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

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

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

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

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

倉庫傳送門：數據結構

我們下篇博客見！😘

總結

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

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