พิจารณาว่าเรามีรายการเชื่อมโยง และเราต้องตรวจสอบว่ามีวงจรหรือไม่ เพื่อแสดงวัฏจักรในรายการที่เชื่อมโยงที่กำหนด เราจะใช้ตัวชี้จำนวนเต็มหนึ่งตัวที่เรียกว่า pos ตำแหน่งนี้แสดงถึงตำแหน่งในรายการเชื่อมโยงที่มีการเชื่อมต่อหาง ดังนั้นหากตำแหน่งเป็น -1 แสดงว่าไม่มีวงจรอยู่ในรายการที่เชื่อมโยง ตัวอย่างเช่น รายการที่เชื่อมโยงเป็นเหมือน [5, 3, 2, 0, -4, 7] และ pos =1 ดังนั้นจึงมีวงจรและส่วนท้ายเชื่อมต่อกับโหนดที่สอง ข้อจำกัดคือเราไม่สามารถแก้ไขรายการได้
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ช้า :=หัวและเร็ว :=หัว
- ในขณะที่ใช้งานได้ช้า เร็ว และถัดไปของเร็ว
- ช้า :=ถัดจากช้า
- เร็ว :=ถัดไปจาก (ถัดไปจากเร็ว)
- ถ้าช้า =เร็วก็แตก
- ถ้า fast ไม่ว่าง หรือ next of first ไม่ว่าง ให้คืนค่า null
- ถ้าช้า =เร็ว แล้ว
- ช้า :=หัว
- ในขณะที่ช้าไม่เร็ว
- ช้า :=ถัดจากช้าและเร็ว :=ถัดจากเร็ว
- กลับช้า
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class ListNode{
public:
int val;
ListNode *next;
ListNode(int data){
val = data;
next = NULL;
}
};
ListNode *make_list(vector<int> v){
ListNode *head = new ListNode(v[0]);
for(int i = 1; i<v.size(); i++){
ListNode *ptr = head;
while(ptr->next != NULL){
ptr = ptr->next;
}
ptr->next = new ListNode(v[i]);
}
return head;
}
ListNode *get_node(ListNode *head, int pos){
ListNode *ptr = head;
if(pos != -1){
int p = 0;
while(p < pos){
ptr = ptr->next;
p++;
}
return ptr;
}
return NULL;
}
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* slow = head;
ListNode* fast = head;
while(slow && fast && fast->next){
slow = slow->next;
fast = fast->next->next;
if(slow == fast)break;
}
if(!fast || !fast->next)return NULL;
if(slow == fast){
slow = head;
while(slow!=fast){
slow = slow->next;
fast = fast->next;
}
}
return slow;
}
};
main(){
Solution ob;
vector<int> v = {5,3,2,0,-4,7};
ListNode *head = make_list(v);
int pos = 1;
ListNode *lastNode = get_node(head, v.size() - 1);
lastNode->next = get_node(head, pos);
cout << "Tail is connected to the node with value:" <<ob.detectCycle(head)->val;
} อินพุต
[5,3,2,0,-4,7] 1
ผลลัพธ์
Tail is connected to the node with value:3
