目錄
題一：環形鏈表
思路一：
題二：復制帶隨機指針的鏈表
?思路一：
本人實力有限可能對一些地方解釋的不夠清晰，可以自己嘗試讀代碼，望海涵！
題一：環形鏈表
給定一個鏈表的頭節點 ?head?，返回鏈表開始入環的第一個節點。?如果鏈表無環，則返回?null。
如果鏈表中有某個節點，可以通過連續跟蹤?next?指針再次到達，則鏈表中存在環。 為了表示給定鏈表中的環，評測系統內部使用整數?pos?來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果?pos?是?-1，則在該鏈表中沒有環。注意：pos?不作為參數進行傳遞，僅僅是為了標識鏈表的實際情況。
不允許修改?鏈表。
示例 1：
思路一：
? ? ? ? 定義快慢指針：slow，fast，slow每次走一步，fast每次走兩步；假設到環口長度為L，環的周長為C，slow從環口到相遇點為S，如下圖：slow走了:L+S fast走了:2*(L+S)；當slow到環口時fast已經走了n圈到相遇時n>=1，所以fast到相遇時走了:L+n*C+S
得出運算式：L = n*C-S，結論：一個指針從起點走，一個從相遇點走，他們會在入口點相遇。
struct ListNode *detectCycle(struct ListNode *head)
{struct ListNode* slow = head;struct ListNode* fast = head;struct ListNode* newnode = head;//判斷有沒有相遇點while(fast && fast->next){slow = slow->next;fast = fast->next->next;//找到相遇點if(slow == fast){struct ListNode* node = slow;//分別從起點和相遇點開始走while(node != newnode){newnode = newnode->next;node = node->next;}return newnode;}}return NULL;
}題二：復制帶隨機指針的鏈表
給你一個長度為?n?的鏈表，每個節點包含一個額外增加的隨機指針?random?，該指針可以指向鏈表中的任何節點或空節點。
構造這個鏈表的?深拷貝。?深拷貝應該正好由?n?個?全新?節點組成，其中每個新節點的值都設為其對應的原節點的值。新節點的?next?指針和?random?指針也都應指向復制鏈表中的新節點，并使原鏈表和復制鏈表中的這些指針能夠表示相同的鏈表狀態。復制鏈表中的指針都不應指向原鏈表中的節點?。
例如，如果原鏈表中有?X?和?Y?兩個節點，其中?X.random --> Y?。那么在復制鏈表中對應的兩個節點?x?和?y?，同樣有?x.random --> y?。
返回復制鏈表的頭節點。
示例 1：
輸入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 輸出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
?思路一：
第一步:在原鏈表的每一個之間開辟一塊相同空間的copy將val和下一個的地址復制，并改變cur->next=copy；
第二步：因為每個原鏈表后面都有一個復制的copy鏈表所以copy-> randon都可以指向自己復制的randon；核心: copy=cur-> randon->next
第三步：將copy鏈表從原鏈表head上分離出來，并將各自的節點接上。
?
?
struct Node* copyRandomList(struct Node* head) {struct Node* cur = head;while(cur){struct Node* next = cur->next;//開辟copy的節點struct Node* copy = (struct Node*)malloc(sizeof(struct Node));//復制值copy->val = cur->val;//插入copy->next = next;cur->next = copy;//向后走cur = next;}cur = head;while(cur){struct Node* copy = cur->next;if(cur->random != NULL){//copy的隨機節點指向自己的隨機節點copy->random = cur->random->next;}else{copy->random = NULL;}cur = copy->next;}//分離鏈表struct Node* copyhead = NULL;struct Node* copytail = NULL;cur = head;while(cur){struct Node* copy = cur->next;struct Node* next = copy->next;//分離copy鏈表if(copytail == NULL){copyhead = copytail = copy;}else{copytail->next = copy;copytail = copytail->next;}//恢復原鏈表cur->next = next;cur = next;}return copyhead;
}
