Fast and Slow Pointers

📘 Fast and Slow Pointers (Floyd’s Tortoise and Hare Algorithm)

1. Lý thuyết cơ bản

1.1. Ý tưởng

  • Sử dụng 2 con trỏ duyệt qua dữ liệu:

    • Slow pointer (chậm): mỗi lần đi 1 bước.

    • Fast pointer (nhanh): mỗi lần đi 2 bước.

  • Khi duyệt:

    • Nếu Fast gặp Slow ⇒ có vòng lặp (cycle).

    • Nếu Fast tới null ⇒ không có vòng lặp.

    • Nếu dùng trong tìm middle node, khi Fast tới cuối, Slow sẽ nằm giữa.

1.2. Ứng dụng chính

  1. Detect cycle trong Linked List (kiểm tra có vòng lặp không).

  2. Find middle node trong Linked List.

  3. Find cycle start node trong Linked List (nâng cao).

  4. Find duplicate number in an array (bài toán LeetCode 287, biểu diễn array như một “linked list ảo”).

  5. Một số bài toán về “meeting point” trong dãy số hoặc chu kỳ.

1.3. Ưu điểm

  • Time complexity: O(n)

  • Space complexity: O(1)

  • Không cần hash set hay visited array.

2. Ví dụ minh họa

🟢 2.1. Detect Cycle in Linked List

Java

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;

        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) return true; // gặp nhau => có cycle
        }
        return false;
    }
}

Golang

type ListNode struct {
    Val  int
    Next *ListNode
}

func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return false
    }

    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            return true
        }
    }
    return false
}

🟢 2.2. Find Middle Node in Linked List

Java

public class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow; // khi fast tới cuối, slow ở giữa
    }
}

Golang

func middleNode(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    return slow
}

🟢 2.3. Find Duplicate Number in Array (LeetCode 287)

Ý tưởng:

  • Dãy nums có n+1 số trong phạm vi [1..n].

  • Có ít nhất một số trùng lặp.

  • Xem mảng như linked list:

    • i → nums[i].

  • Sẽ có một “cycle” ⇒ dùng fast/slow tìm điểm gặp.

Java

public class Solution {
    public int findDuplicate(int[] nums) {
        int slow = nums[0];
        int fast = nums[0];

        // Phase 1: tìm điểm gặp nhau trong cycle
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        // Phase 2: tìm entry point của cycle (chính là số trùng)
        fast = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
}

Golang

func findDuplicate(nums []int) int {
    slow, fast := nums[0], nums[0]

    // Phase 1: tìm điểm gặp
    for {
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast {
            break
        }
    }

    // Phase 2: tìm entry point
    fast = nums[0]
    for slow != fast {
        slow = nums[slow]
        fast = nums[fast]
    }
    return slow
}

3. Tổng kết

  • Fast & Slow Pointers = 2 con trỏ chạy với tốc độ khác nhau.

  • Công dụng: ✅ Tìm vòng lặp trong Linked List. ✅ Tìm node giữa trong Linked List. ✅ Tìm điểm bắt đầu của cycle. ✅ Giải bài toán tìm số trùng trong mảng.

  • Ưu điểm: chạy nhanh, không tốn thêm bộ nhớ.

PreviousDSANextAWS

Last updated