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

3.1 Fast & Slow Pointers

চিনবেন কীভাবে
"detect cycle", "middle of list", "nth from end", "intersection" — two pointers at different speeds or a fixed gap
Demo · approach · কোড — আগে নিজে চেষ্টা, আটকালে খুলুন

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

Statement (Demo): Given the head of a linked list, return the node where the cycle begins, or null if there is no cycle. Use O(1) space. Example: head=[3,2,0,-4], tail connects to index 1 → node with value 2 | ⚡ n ≤ 10⁴

Approach: Fast moves 2 steps, slow moves 1 — if they meet, there is a cycle. Then move one pointer back to head and step both one at a time; where they meet again is the cycle's start (math: distance head→start = distance meeting→start, mod cycle length).

function detectCycle(head) {
  let slow = head,
    fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      // cycle found
      let p = head;
      while (p !== slow) {
        p = p.next;
        slow = slow.next;
      }
      return p; // start of the cycle
    }
  }
  return null;
}

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

প্রবলেম

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

    Statement: Given the head of a linked list, return true if it has a cycle (some node's next points back to an earlier node), otherwise false.
    Example: head=[3,2,0,-4], tail connects to index 1 → true | ⚡ n ≤ 10⁴

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

    Statement: Given the head of a singly linked list, return its middle node. With two middles, return the second.
    Example: [1,2,3,4,5] → node 3 | ⚡ n ≤ 100

    নোট · ফাঁকা
  • Remove Nth Node From End of Listplan · দিন ০১৮LC 19
    (two pointers n apart + dummy)

    Statement: Given the head of a linked list and an integer n, remove the n-th node from the end and return the head. Do it in one pass.
    Example: [1,2,3,4,5], n=2 → [1,2,3,5] | ⚡ n ≤ 30

    নোট · ফাঁকা