Əsas məzmuna keçin

Fast & Slow Pointers

Fast & Slow Pointers pattern-i, xüsusilə linked list-lərlə işləyərkən istifadə olunan effektiv bir üsuldur. Bu pattern, biri digərindən daha sürətli hərəkət edən iki pointer istifadə edir. Adətən, sürətli pointer yavaş pointerdən iki dəfə daha sürətli hərəkət edir. Bu pattern, Floyd's Cycle-Finding Algorithm və ya "Tortoise and Hare Algorithm" kimi də tanınır.

Pattern-in Əsas Xüsusiyyətləri​

  • İki Fərqli Sürətli Pointer: Bir yavaş (slow) və bir sürətli (fast) pointer
  • Sürət Fərqi: Adətən fast pointer, slow pointer-dən iki dəfə daha sürətli hərəkət edir
  • Yaddaş Effektivliyi: O(1) əlavə yaddaş istifadə edir
  • Dövr Tapma: Xüsusilə linked list-lərdə dövr aşkarlamaq üçün effektivdir

Fast & Slow Pointers Pattern-in Tətbiq Sahələri​

  1. Cycle Detection: Linked list-də dövr olub-olmadığını aşkarlamaq
  2. Cycle Start Point: Dövrün başlanğıc nöqtəsini tapmaq
  3. Middle of Linked List: Linked list-in ortasını tapmaq
  4. Palindrome Linked List: Linked list-in palindrome olub-olmadığını yoxlamaq
  5. Nth Node From End: Linked list-in sonundan n-ci node-u tapmaq

Nümunə Problemlər və Həllər​

1. Linked List-də Dövr Aşkarlama​

Problem: Verilmiş linked list-də dövr olub-olmadığını təyin edin.

Həll:

Koda bax
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;          // 1 addım irəli
        fast = fast.next.next;     // 2 addım irəli
        
        if (slow == fast) {        // Əgər pointerlər görüşürsə, dövr var
            return true;
        }
    }
    
    return false;                  // Fast pointer sona çatdı, dövr yoxdur
}

2. Dövrün Başlanğıc Nöqtəsini Tapmaq​

Problem: Linked list-də dövr varsa, dövrün başlanğıc nöqtəsini tapın.

Həll:

Koda bax
public ListNode detectCycle(ListNode head) {
    if (head == null || head.next == null) {
        return null;
    }
    
    // Dövr aşkarlama
    ListNode slow = head;
    ListNode fast = head;
    boolean hasCycle = false;
    
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        
        if (slow == fast) {
            hasCycle = true;
            break;
        }
    }
    
    if (!hasCycle) {
        return null;
    }
    
    // Dövrün başlanğıcını tapmaq
    slow = head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    
    return slow;  // Dövrün başlanğıc nöqtəsi
}

3. Linked List-in Ortasını Tapmaq​

Problem: Linked list-in ortasındakı node-u tapın.

Həll:

Koda bax
public ListNode middleNode(ListNode head) {
    if (head == null) {
        return null;
    }
    
    ListNode slow = head;
    ListNode fast = head;
    
    while (fast != null && fast.next != null) {
        slow = slow.next;          // 1 addım irəli
        fast = fast.next.next;     // 2 addım irəli
    }
    
    return slow;  // Orta node
}

4. Palindrome Linked List​

Problem: Linked list-in palindrome olub-olmadığını yoxlayın.

Həll:

Koda bax
public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) {
        return true;
    }
    
    // Orta nöqtəni tapmaq
    ListNode slow = head;
    ListNode fast = head;
    
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // İkinci yarını çevirmək
    ListNode secondHalf = reverseList(slow.next);
    ListNode firstHalf = head;
    
    // İki yarını müqayisə etmək
    while (secondHalf != null) {
        if (firstHalf.val != secondHalf.val) {
            return false;
        }
        firstHalf = firstHalf.next;
        secondHalf = secondHalf.next;
    }
    
    return true;
}

private ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode current = head;
    
    while (current != null) {
        ListNode next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    
    return prev;
}

Zaman və Yaddaş Mürəkkəbliyi​

  • Zaman Mürəkkəbliyi: Əksər hallarda O(n), burada n linked list-in uzunluğudur
  • Yaddaş Mürəkkəbliyi: O(1), çünki yalnız bir neçə pointer istifadə olunur