Linked List Cycle II - หาจุดเริ่มต้นของวงจรใน C++

ภาพรวมปัญหา

มี Linked List ต้องตรวจสอบว่ามีวงจร (cycle) หรือไม่ ใช้ตัวแปร pos แทนตำแหน่งที่ tail เชื่อมต่อ (pos = -1 หมายถึงไม่มีวงจร) ห้ามแก้ไขโครงสร้างลิสต์

ตัวอย่าง: [5, 3, 2, 0, -4, 7], pos = 1 → tail เชื่อมต่อที่โหนดที่ 2 (ค่า 3)

อัลกอริทึม Floyd's Cycle Detection (Tortoise and Hare)

1. slow := head, fast := head
2. while slow, fast และ fast->next มีอยู่:
   • slow := slow->next
   • fast := fast->next->next
   • ถ้า slow == fast → break
3. ถ้า fast ว่างหรือ fast->next ว่าง → return null (ไม่มีวงจร)
4. ถ้า slow == fast:
   • slow := head
   • while slow != fast: slow := slow->next, fast := fast->next
5. return slow (จุดเริ่มต้นของวงจร)

ตัวอย่างโค้ด C++

#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;
    }
};

int 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;
}

Input / Output

Input:  [5,3,2,0,-4,7] 1
Output: Tail is connected to the node with value: 3