মূল কনটেন্টে যান
🧩
লোকাল DSA
প্যাটার্ন•টপিক 3 · Linked Lists

3.1 Fast & Slow Pointers

চিনবেন কীভাবে
"detect cycle", "middle of list", "nth from end", "intersection" — দুই pointer ভিন্ন গতিতে/ব্যবধানে
Demo · approach · কোড — আগে নিজে চেষ্টা, আটকালে খুলুন

Demo: Linked List Cycle II — LC 142 (Medium — Amazon/Meta/Google High)

Statement (Demo): linked list-এর head দেওয়া — cycle থাকলে cycle শুরু হওয়ার নোড return করুন, না থাকলে null। O(1) space-এ করতে হবে। উদাহরণ: head=[3,2,0,-4], tail connects to index 1 → node with value 2 | ⚡ n ≤ 10⁴

Approach: fast ২ ধাপ, slow ১ ধাপ — দেখা হলে cycle আছে। এরপর একটা pointer head-এ ফিরিয়ে দুটোই ১ ধাপ করে চালান; আবার যেখানে মিলবে সেটাই cycle-এর শুরু (গণিত: head→start দূরত্ব = meeting→start দূরত্ব mod cycle)।

function detectCycle(head) {
  let slow = head,
    fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      // cycle পাওয়া গেছে
      let p = head;
      while (p !== slow) {
        p = p.next;
        slow = slow.next;
      }
      return p; // cycle-এর শুরুর নোড
    }
  }
  return null;
}

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

প্রবলেম

  • Linked List Cycleplan · দিন ০১৯LC 141

    Statement: linked list-এর head দেওয়া — list-এ cycle আছে কিনা true/false return করুন। (cycle = কোনো নোডের next আগের কোনো নোডে পয়েন্ট করে।)
    উদাহরণ: head=[3,2,0,-4], tail connects to index 1 → true | ⚡ n ≤ 10⁴

    নোট · ফাঁকা
  • Middle of the Linked Listplan · দিন ০১৮LC 876

    Statement: singly linked list-এর head দেওয়া — middle node return করুন। দুটো middle থাকলে দ্বিতীয়টা return করুন।
    উদাহরণ: [1,2,3,4,5] → node 3 | ⚡ n ≤ 100

    নোট · ফাঁকা
  • Remove Nth Node From End of Listplan · দিন ০২২LC 19
    (n ব্যবধানে দুই pointer + dummy)

    Statement: linked list-এর head ও integer n দেওয়া — শেষ থেকে n-তম নোড সরিয়ে দিন। modified list-এর head return করুন। one pass-এ করতে হবে।
    উদাহরণ: [1,2,3,4,5], n=2 → [1,2,3,5] | ⚡ n ≤ 30

    নোট · ফাঁকা