Fast & Slow Pointers: Phát hiện vòng lặp bằng thuật toán Floyd

Fast & Slow Pointers: Phát hiện vòng lặp bằng thuật toán Floyd | Shanverse

Codetypescript

1function hasCycle<T>(head: ListNode<T> | null): boolean {2  let slow = head;3  let fast = head;45  while (fast !== null && fast.next !== null) {6    slow = slow!.next;7    fast = fast.next.next;89    if (slow === fast) {10      return true;11    }12  }1314  return false;15}

Codetypescript

1function findMeetingPoint<T>(2  head: ListNode<T> | null,3): ListNode<T> | null {4  let slow = head;5  let fast = head;67  while (fast !== null && fast.next !== null) {8    slow = slow!.next;9    fast = fast.next.next;1011    if (slow === fast) return slow;12  }1314  return null;15}

Codetypescript

1function findCycleEntry<T>(2  head: ListNode<T> | null,3): ListNode<T> | null {4  const meeting = findMeetingPoint(head);5  if (meeting === null) return null;67  let fromHead = head;8  let fromMeeting: ListNode<T> | null = meeting;910  while (fromHead !== fromMeeting) {11    fromHead = fromHead!.next;12    fromMeeting = fromMeeting!.next;13  }1415  return fromHead;16}

Codetypescript

1function getCycleLength<T>(2  head: ListNode<T> | null,3): number {4  const meeting = findMeetingPoint(head);5  if (meeting === null) return 0;67  let length = 1;8  let cursor = meeting.next;910  while (cursor !== meeting) {11    cursor = cursor!.next;12    length++;13  }1415  return length;16}

Codetypescript

1type CycleInfo<T> = {2  hasCycle: boolean;3  entry: ListNode<T> | null;4  cycleLength: number;5  tailLength: number;6};78function analyzeCycle<T>(head: ListNode<T> | null): CycleInfo<T> {9  const meeting = findMeetingPoint(head);1011  if (meeting === null) {12    return {13      hasCycle: false,14      entry: null,15      cycleLength: 0,16      tailLength: 0,17    };18  }1920  let cycleLength = 1;21  let cursor = meeting.next!;22  while (cursor !== meeting) {23    cursor = cursor.next!;24    cycleLength++;25  }2627  let fromHead = head!;28  let fromMeeting = meeting;29  let tailLength = 0;3031  while (fromHead !== fromMeeting) {32    fromHead = fromHead.next!;33    fromMeeting = fromMeeting.next!;34    tailLength++;35  }3637  return {38    hasCycle: true,39    entry: fromHead,40    cycleLength,41    tailLength,42  };43}

Codetypescript

1const a: ListNode<string> = { value: "A", next: null };2const b: ListNode<string> = { value: "B", next: null };3const c: ListNode<string> = { value: "C", next: null };4const d: ListNode<string> = { value: "D", next: null };5const e: ListNode<string> = { value: "E", next: null };67a.next = b;8b.next = c;9c.next = d;10d.next = e;11e.next = c;1213const info = analyzeCycle(a);14console.log(info.hasCycle);    // true15console.log(info.entry?.value); // C16console.log(info.cycleLength);  // 3: C → D → E → C17console.log(info.tailLength);   // 2: A → B

Codetypescript

1type Next<State> = (state: State) => State | null;2type Equals<State> = (left: State, right: State) => boolean;34function findCycleMeeting<State>(5  start: State | null,6  next: Next<State>,7  equals: Equals<State> = Object.is,8): State | null {9  let slow = start;10  let fast = start;1112  while (fast !== null) {13    slow = slow === null ? null : next(slow);1415    const fastOnce = next(fast);16    fast = fastOnce === null ? null : next(fastOnce);1718    if (slow === null || fast === null) return null;19    if (equals(slow, fast)) return slow;20  }2122  return null;23}

Codetypescript

1function nextHappyValue(value: number): number {2  let remaining = value;3  let sum = 0;45  while (remaining > 0) {6    const digit = remaining % 10;7    sum += digit * digit;8    remaining = Math.floor(remaining / 10);9  }1011  return sum;12}1314function isHappyNumber(value: number): boolean {15  let slow = value;16  let fast = value;1718  do {19    slow = nextHappyValue(slow);20    fast = nextHappyValue(nextHappyValue(fast));21  } while (slow !== fast);2223  return slow === 1;24}

Codetypescript

1type DetectionResult<T> =2  | { kind: "cycle"; meeting: ListNode<T> }3  | { kind: "acyclic" }4  | { kind: "limit-reached" };56function detectWithLimit<T>(7  head: ListNode<T> | null,8  maxIterations: number,9): DetectionResult<T> {10  let slow = head;11  let fast = head;1213  for (let iteration = 0; iteration < maxIterations; iteration++) {14    if (fast === null || fast.next === null) {15      return { kind: "acyclic" };16    }1718    slow = slow!.next;19    fast = fast.next.next;2021    if (slow === fast) {22      return { kind: "cycle", meeting: slow! };23    }24  }2526  return { kind: "limit-reached" };27}

Codetypescript

1function middleNode<T>(head: ListNode<T> | null): ListNode<T> | null {2  let slow = head;3  let fast = head;45  while (fast !== null && fast.next !== null) {6    slow = slow!.next;7    fast = fast.next.next;8  }910  return slow;11}

Bài toán

Comments

Phase 1: phát hiện có cycle

Guard phải kiểm tra đúng thứ tự

Trả về meeting point

Vì sao hai con trỏ chắc chắn gặp nhau?

Phase 2: tìm cycle entry

Trực giác toán học

Phase 3: đo cycle length

Phân tích đầy đủ cycle

Ví dụ dựng Linked List có cycle

Độ phức tạp chính xác hơn

So sánh Floyd với Set

Floyd trên Functional Graph

Generic implementation có trạng thái kết thúc

Ví dụ: Happy Number

“Luồng dữ liệu” nào dùng được Floyd?

Vì sao?

Khi Floyd không phù hợp

Graph có nhiều nhánh

Nondeterministic transition

Structure đang bị mutate

Cần đường đi đầy đủ

Infinite acyclic sequence

Version có budget

Các ứng dụng khác của Fast & Slow Pointers

Tìm middle của Linked List

Kiểm tra palindrome Linked List

Tìm k-th node từ cuối

Lỗi thường gặp

1. So sánh value thay vì node

2. Dereference fast.next.next không guard

3. Reset sai pointer khi tìm entry

4. Meeting point bị hiểu là entry

5. Dùng cho graph branching

6. Cho rằng dữ liệu lặp nghĩa là state cycle

7. Không đặt budget cho sequence không bảo đảm hữu hạn

8. Mutate list để “đánh dấu” node

Edge cases cần test

Cách tiếp cận chuẩn

Kết luận

Related posts

Monotonic Stack & Queue: Tìm phần tử lớn hơn hoặc nhỏ hơn tiếp theo trong O(N)

Two Pointers Pattern: Đảo mảng, kiểm tra chuỗi đối xứng và tìm cặp số

Trie (Prefix Tree): Xây dựng Search Suggestion và Autocomplete siêu tốc