💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤
📃個人主頁 ：阿然成長日記 👈點擊可跳轉
📆 個人專欄： 🔹數據結構與算法🔹C語言進階
🚩 不能則學，不知則問，恥于問人，決無長進
🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍

前言：

最近在刷題的鐵子們，你們在做題的時候一定要畫圖，人的思維固然很強，但是把圖畫好是真香啊！遇到BUGl了照著圖分析，十分簡潔明朗，事半功倍。

鏈表的回文結構

題目：對于一個鏈表，請設計一個時間復雜度為O(n),額外空間復雜度為O(1)的算法，判斷其是否為回文結構。給定一個鏈表的頭指針A，請返回一個bool值，代表其是否為回文結構。保證鏈表長度小于等于900。

測試樣例： 1->2->2->1 返回：true

思路：
1.找到中間節點
2.從中間節點往后逆置
3.定義快慢指針，向后遍歷判斷是否相等。

class PalindromeList {
public: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;}struct ListNode* reveseList(struct ListNode* head){struct ListNode* cur = head;struct ListNode* newhead = nullptr;while(cur){struct ListNode* next = cur->next;cur->next = newhead;newhead  = cur;cur = next;} return newhead;} bool chkPalindrome(ListNode* head) {// write code herestruct ListNode* mid = middleNode(head);struct ListNode* rmid = reveseList(mid);while(rmid && head){if(rmid->val !=head->val){return false;}rmid = rmid->next;head = head->next;}return true;}
};

160.相交鏈表

題目：

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

題目數據 保證 整個鏈式結構中不存在環。

注意，函數返回結果后，鏈表必須 保持其原始結構 。

自定義評測：

評測系統 的輸入如下（你設計的程序 不適用 此輸入）：

intersectVal - 相交的起始節點的值。如果不存在相交節點，這一值為 0 listA - 第一個鏈表 listB - 第二個鏈表
skipA - 在 listA 中（從頭節點開始）跳到交叉節點的節點數 skipB - 在 listB
中（從頭節點開始）跳到交叉節點的節點數 評測系統將根據這些輸入創建鏈式數據結構，并將兩個頭節點 headA 和 headB
傳遞給你的程序。如果程序能夠正確返回相交節點，那么你的解決方案將被 視作正確答案 。

思路：
1.分別計算listA,listB鏈表的長度
2.取兩絕對值，對齊兩個鏈表，同時開始遍歷，當相同就相交了。

代碼：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* curA = headA,*curB = headB;//分別計算A，B鏈表的長度int lenA =1,lenB =1;while(curA->next){curA = curA->next;lenA++;}while(curB->next){curB = curB->next;lenB++;}//此時curA，B都已指向最后節點，如果不相等，則說明不相交if(curA != curB){return NULL;}//求出相差的步數int n = abs(lenA-lenB);struct ListNode* LongList = headA,* ShortList = headB;if(lenA<lenB){LongList = headB;ShortList = headA;}//先讓長的鏈表走n步，與短鏈表對齊while(n--){LongList = LongList->next;}//同時走，找相同；while(LongList!=ShortList){LongList = LongList->next;ShortList = ShortList->next;}return ShortList;
}

141.環形鏈表（LeetCode）

給你一個鏈表的頭節點 ，判斷鏈表中是否有環。head

如果鏈表中有某個節點，可以通過連續跟蹤 指針再次到達，則鏈表中存在環。為了表示給定鏈表中的環，評測系統內部使用整數 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。注意：pos 不作為參數進行傳遞 。僅僅是為了標識鏈表的實際情況。nextpos

如果鏈表中存在環 ，則返回 。否則，返回 。truefalse

思路：

代碼：

bool hasCycle(struct ListNode *head) {struct ListNode *fast = head,*low = head;while(fast && fast->next){fast = fast->next->next;low = low->next;if(fast == low){return true;}}return false;
}

leetcode142.環形鏈||

題目要求：

給定一個鏈表的頭節點 head ，返回鏈表開始入環的第一個節點。 如果鏈表無環，則返回 null。

如果鏈表中有某個節點，可以通過連續跟蹤 next 指針再次到達，則鏈表中存在環。 為了表示給定鏈表中的環，評測系統內部使用整數 pos來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果 pos 是 -1，則在該鏈表中沒有環。
注意：pos不作為參數進行傳遞，僅僅是為了標識鏈表的實際情況。不允許修改 鏈表。

思路分析：
🔸如果鏈表存在環，則fast和slow會在環內相遇，定義相遇點到入口點的距離為X,定義環的長度為C,定義頭到入口的距離為L,fast在slow進入環之后一圈內追上slow,則會得知：
🔸slow所走的步數為:L + X
🔸fast所走的步數為：L + X + N * C
并且fast所走的步數為slow的兩倍，故：
🔸2*(L + X) = L + X + N * C
即： L = N * C - X
所以從相遇點開始slow繼續走，讓一個指針從頭開始走，相遇點即為入口節點

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

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

題目要求：

·讀題·：首先，這道題目的意思是完整的復制一遍鏈表，難點在于每個節點有一個隨機指針，由于題目要求不能指向原來鏈表，所以他的復制成了一個難點。

解決步驟：
1.在原鏈表每個節點之后插入一個復制節點 （復制前一個節點）。
2.給復制節點中的random進行指向。
3.把所有的復制節點拿下來整理成新列表，
思路圖：

代碼：

struct Node* copyRandomList(struct Node* head) {struct Node* cur = head;//復制每個節點并插入到相應節點之后while(cur){struct Node* next = cur->next;struct Node* copy = (struct Node*)malloc(sizeof(struct Node));//給copy賦值內容copy->val = cur->val;//插入cur->next = copy;copy->next = next;//向后移動過cur指針和next指針cur = next;}//處理random指向cur = head;while(cur){struct Node* copy = cur->next;if(cur->random==NULL){copy->random = NULL;}else{//精華所在copy->random = cur->random->next;//指向原鏈表的復制節點}cur = copy->next;}//將新鏈表整理出來cur = head;//制造一個哨兵位作為新鏈表的頭結點，便于插入 struct Node* copyhead = (struct Node*)malloc(sizeof(struct Node));copyhead->val = 1;copyhead->next = NULL;copyhead->random = NULL;//定義一個節點，遍歷新鏈表。為了保存原鏈表的頭。struct Node* pcopyhead = copyhead;while(cur){struct Node* copy = cur->next;struct Node* next = copy->next;//尾插到新鏈表pcopyhead->next = copy;pcopyhead = pcopyhead->next;//恢復原鏈表cur->next = next;cur = next;}return copyhead->next;
}

注意點：切記如果使用了哨兵位那么一定要給它進行初始化。