Java Program ตรวจจับ Loop ใน LinkedList (Cycle Detection)

Loop ใน LinkedList คืออะไร?

Loop (Cycle) ใน Linked List เกิดขึ้นเมื่อ Node สุดท้าย (หรือ Node กลาง) ชี้กลับไปยัง Node ก่อนหน้า ทำให้เกิดวงจรปิด (Cycle) การ Traverse ปกติจะติด Infinite Loop

อัลกอริทึมการตรวจจับ Loop

วิธีที่ 1: HashSet (เก็บ Node ที่ผ่านมา)

Time: O(n), Space: O(n)

• สร้าง HashSet เก็บ Node ที่เคยเข้าเยี่ยม
• Traverse linked list ทีละ Node
• ถ้า Node ปัจจุบันอยู่ใน Set แล้ว → มี Loop
• ถ้าถึง null → ไม่มี Loop

วิธีที่ 2: Floyd's Cycle Detection (Tortoise & Hare) - แนะนำ

Time: O(n), Space: O(1)

• ใช้ 2 Pointers: Slow (กछู) เดินทีละ 1, Fast (กระต่าย) เดินทีละ 2
• ถ้ามี Loop → Fast จะ追ทัน Slow ที่จุดใดจุดหนึ่ง
• ถ้าไม่มี Loop → Fast จะถึง null ก่อน

ตัวอย่างที่ 1: ใช้ HashSet (Traversal Method)

import java.util.*;

public class Demo {
    static Node head;
    
    static class Node {
        int data;
        Node next;
        Node(int d) { data = d; next = null; }
    }
    
    static public void push(int newData) {
        Node newNode = new Node(newData);
        newNode.next = head;
        head = newNode;
    }
    
    static boolean checkLoop(Node head) {
        HashSet visited = new HashSet<>();
        while (head != null) {
            if (visited.contains(head)) {
                return true; // พบ Loop
            }
            visited.add(head);
            head = head.next;
        }
        return false;
    }
    
    public static void main(String[] args) {
        System.out.println("The required packages have been imported");
        Demo list = new Demo();
        
        list.push(45);
        list.push(60);
        list.push(75);
        list.push(90);
        
        // สร้าง Loop: Node สุดท้ายชี้กลับไป head
        list.head.next.next.next.next = list.head;
        
        if (checkLoop(head))
            System.out.println("The loop exists in the linked list");
        else
            System.out.println("The loop does not exist in the linked list");
    }
}

ผลลัพธ์

The required packages have been imported
The loop exists in the linked list

ตัวอย่างที่ 2: Floyd's Algorithm (Two Pointers) - Space O(1)

public class Demo {
    Node head;
    
    static class Node {
        int value;
        Node next;
        Node(int d) { value = d; next = null; }
    }
    
    // Floyd's Cycle Detection Algorithm
    public boolean checkLoop() {
        Node slow = head;      // กछู - เดินทีละ 1
        Node fast = head;      // กระต่าย - เดินทีละ 2
        
        while (fast != null && fast.next != null) {
            slow = slow.next;          // 1 step
            fast = fast.next.next;     // 2 steps
            
            if (slow == fast) {
                return true; // พบ Loop
            }
        }
        return false; // ไม่มี Loop
    }
    
    public static void main(String[] args) {
        Demo list = new Demo();
        
        // สร้าง LinkedList: 45 -> 60 -> 75 -> 90
        list.head = new Node(45);
        Node second = new Node(60);
        Node third = new Node(75);
        Node fourth = new Node(90);
        
        list.head.next = second;
        second.next = third;
        third.next = fourth;
        
        // สร้าง Loop: 90 ชี้กลับไป 60
        fourth.next = second;
        
        // แสดงข้อมูล (ระวัง Infinite Loop!)
        System.out.print("The elements of the linked list are: ");
        int i = 1;
        Node current = list.head;
        while (i <= 4) { // แสดงแค่ 4 ตัวแรก
            System.out.print(current.value + " ");
            current = current.next;
            i++;
        }
        
        boolean loop = list.checkLoop();
        if (loop) {
            System.out.println("\nThere is a loop in the linked list.");
        } else {
            System.out.println("\nThere is no loop in the linked list.");
        }
    }
}

ผลลัพธ์

The elements of the linked list are: 45 60 75 90
There is a loop in the linked list.

การหาจุดเริ่มต้นของ Loop (Finding Loop Start)

หลังจากพบ Loop ด้วย Floyd's Algorithm สามารถหาจุดเริ่มต้นได้:

public Node findLoopStart() {
    Node slow = head;
    Node fast = head;
    
    // Phase 1: หาจุดพบกัน
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) break;
    }
    
    // ไม่มี loop
    if (fast == null || fast.next == null) return null;
    
    // Phase 2: หาจุดเริ่มต้น
    slow = head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow; // จุดเริ่มต้นของ Loop
}

การหาความยาวของ Loop

public int getLoopLength() {
    Node slow = head, fast = head;
    
    // หาจุดพบกัน
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) break;
    }
    if (fast == null || fast.next == null) return 0;
    
    // นับความยาว
    int length = 1;
    fast = fast.next;
    while (slow != fast) {
        fast = fast.next;
        length++;
    }
    return length;
}

เปรียบเทียบวิธีการ

สรุป

• Loop ใน LinkedList = Node ชี้กลับสร้าง Cycle
• วิธีมาตรฐาน: Floyd's Cycle Detection (Two Pointers) - O(n) time, O(1) space
• วิธี HashSet: เข้าใจง่าย แต่อยาก Memory O(n)
• สามารถหาจุดเริ่มต้นและความยาว Loop เพิ่มเติมได้