Java Program หา Element กลางของ LinkedList ในรอบเดียว (Single Pass)

ปัญหา: หา Node กลางของ LinkedList

LinkedList ไม่มี Random Access (ไม่มี get(index) O(1)) วิธีธรรมดาคือ นับจำนวน Node ก่อน (1 pass) แล้วเดินไปครึ่งหนึ่ง (อีก 1 pass) = 2 Passes

Two Pointer Technique (Slow & Fast Pointers) ทำได้ใน 1 Pass O(n) Time, O(1) Space

อัลกอริทึม Two Pointers (Tortoise & Hare)

1. สร้าง 2 Pointers: slow และ fast เริ่มที่ Head
2. slow เดินทีละ 1 Node, fast เดินทีละ 2 Nodes
3. เมื่อ fast ถึงปลาย (null หรือ next เป็น null) → slow จะอยู่ที่ Node กลาง

กรณีคี่ (Odd Length): 1→2→3→4→5

Slow: 1 → 2 → 3 (Middle)
Fast: 1 → 3 → 5 → null (Stop)
Middle = 3

กรณีคู่ (Even Length): 1→2→3→4→5→6

Slow: 1 → 2 → 3 (First Middle)
Fast: 1 → 3 → 5 → null (Stop)
Middle = 3 (First middle of two)

ตัวอย่างที่ 1: ใน main โดยตรง

public class LinkedList {
    Node head;
    
    static class Node {
        int value;
        Node next;
        Node(int d) { value = d; next = null; }
    }
    
    public static void main(String[] args) {
        LinkedList inputList = new LinkedList();
        
        // สร้าง List: 100 → 200 → 330
        inputList.head = new Node(100);
        Node second = new Node(200);
        Node third = new Node(330);
        
        inputList.head.next = second;
        second.next = third;
        
        // แสดง List
        Node current = inputList.head;
        System.out.print("The linked list is defined as: ");
        while (current != null) {
            System.out.print(current.value + " ");
            current = current.next;
        }
        
        // Two Pointer Technique
        Node slow = inputList.head;
        Node fast = inputList.head;
        
        while (fast != null && fast.next != null) {
            fast = fast.next.next;  // Fast เดิน 2 ก้าว
            if (fast != null) {     // ตรวจสอบก่อนย้าย Slow
                slow = slow.next;   // Slow เดิน 1 ก้าว
            }
        }
        
        System.out.println("\nThe middle element of the list is: " + slow.value);
    }
}

ผลลัพธ์

The linked list is defined as: 100 200 330
The middle element of the list is: 200

ตัวอย่างที่ 2: แยกเป็นเมธอด (OOP)

public class LinkedList {
    Node head;
    
    static class Node {
        int value;
        Node next;
        Node(int d) { value = d; next = null; }
    }
    
    // เมธอดหา Middle Element
    static void getMiddleItem(LinkedList list) {
        Node slow = list.head;
        Node fast = list.head;
        
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            if (fast != null) {
                slow = slow.next;
            }
        }
        
        System.out.println("\nThe middle element of the list is: " + slow.value);
    }
    
    public static void main(String[] args) {
        LinkedList inputList = new LinkedList();
        inputList.head = new Node(100);
        Node second = new Node(200);
        Node third = new Node(330);
        
        inputList.head.next = second;
        second.next = third;
        
        Node current = inputList.head;
        System.out.print("The linked list is defined as: ");
        while (current != null) {
            System.out.print(current.value + " ");
            current = current.next;
        }
        
        getMiddleItem(inputList);
    }
}

Java Built-in: LinkedList.get(size/2)

java.util.LinkedList มี get(int index) แต่เป็น O(n) ต้อง Traverse จาก Head หรือ Tail

// ใช้ Built-in (ยังคงเป็น O(n) แต่เขียนสั้น)
LinkedList list = new LinkedList<>(Arrays.asList(100, 200, 330));
int middle = list.get(list.size() / 2); // O(n) - Traverse จาก Head/Tail
System.out.println(middle); // 200

Variations: หาจุดเริ่มต้นของ Loop (Cycle Detection)

Two Pointers ยังใช้หาจุดเริ่ม Loop ได้ (Floyd's Algorithm):

// Phase 1: Detect Loop
slow = head; fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) break; // Loop detected
}

// Phase 2: Find Loop Start
if (fast != null && fast.next != null) {
    slow = head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    // slow/fast ตอนนี้คือ Start of Loop
}

การประยุกต์ใช้ Two Pointers อื่นๆ

สรุป

• Two Pointer (Slow/Fast) หา Middle Element ใน 1 Pass O(n) Time, O(1) Space
• Slow เดิน 1 ก้าว, Fast เดิน 2 ก้าว
• เมื่อ Fast ถึงปลาย Slow อยู่กลาง
• Odd Length: Middle จริง | Even Length: First Middle (Lower Middle)
• Technique นี้ใช้กันทั่วไปใน LinkedList Problems (LeetCode, Interviews)