演算法訓練營
- 環形鏈表
- 環形鏈表Ⅱ
- 復制帶隨機指標的鏈表
環形鏈表
解題思路：
這道題我們使用快慢指標的方法，如果有節點，快指標走到會回頭于慢指標匯合，根據這個思想我們解答一下這個題目，
bool hasCycle(struct ListNode *head) {
if (head == NULL || head->next == NULL)
{
return false;
}
ListNode* slow = head;
ListNode* fast = head->next;
while (slow!=fast)
{
if (fast == NULL || fast->next == NULL)
return false;
slow = slow->next;
fast = fast->next->next;
}
return true;
}
環形鏈表Ⅱ
解題思路：
假設鏈表環前有 aa 個節點，環內有 bb 個節點
本題核心思路：走 a+nba+nb 步一定處于環的入口位置
利用快慢指標 fast 和 slow，fast 一次走兩步，slow 一次走一步
當兩個指標第一次相遇時，假設 slow走了 ss 步，下面計算 fast 走過的步數
i. fast 比 slow 多走了 nn 個環：f = s + nbf=s+nb
ii. fast 比 slow 多走一倍的步數：f = 2sf=2s --> 跟上式聯立可得 s = nbs=nb
iii. 綜上計算得，f = 2nbf=2nb，s = nbs=nb
也就是兩個指標第一次相遇時，都走過了環的倍數，那么再走 aa 步就可以到達環的入口
讓 fast 從頭再走，slow 留在原地，fast 和 slow均一次走一步，當兩個指標第二次相遇時，fast 走了 aa 步，slow 走了 a+nba+nb 步
此時 slow 就在環的入口處，回傳 slow
struct ListNode *detectCycle(struct ListNode *head) {
if (head == NULL || head->next == NULL)
{
return false;
}
ListNode* slow = head;
ListNode* fast = head->next;
while (fast != NULL)
{
slow = slow->next;
if (fast->next == NULL)
{
return NULL;
}
fast = fast->next->next;
if (fast == slow)
{
ListNode* ptr = head;
while (ptr != slow)
{
ptr = ptr->next;
slow = slow->next;
}
return ptr;
}
return NULL;
}
復制帶隨機指標的鏈表
解題思路：
我們首先將該鏈表中每一個節點拆分為兩個相連的節點這樣，我們可以直接找到每一個拷貝節點 的隨機指標應當指向的節點，即為其原節點的隨機指標指向的節點 的后繼節點需要注意原節點的隨機指標可能為空，我們需要特別判斷這種情況，
當我們完成了拷貝節點的隨機指標的賦值，我們只需要將這個鏈表按照原節點與拷貝節點的種類進行拆分即可，只需要遍歷一次，同樣需要注意最后一個拷貝節點的后繼節點為空，我們需要特別判斷這種情況，
class Solution {
public:
Node* copyRandomList(Node* head) {
if (head == nullptr) {
return nullptr;
}
for (Node* node = head; node != nullptr; node = node->next->next) {
Node* nodeNew = new Node(node->val);
nodeNew->next = node->next;
node->next = nodeNew;
}
for (Node* node = head; node != nullptr; node = node->next->next) {
Node* nodeNew = node->next;
nodeNew->random = (node->random != nullptr) ? node->random->next : nullptr;
}
Node* headNew = head->next;
for (Node* node = head; node != nullptr; node = node->next) {
Node* nodeNew = node->next;
node->next = node->next->next;
nodeNew->next = (nodeNew->next != nullptr) ? nodeNew->next->next : nullptr;
}
return headNew;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/299384.html
標籤：其他