কনটেন্টে যান

003 — Linked List Cycle

Problem link ও উৎস

  • Original source: Classic linked list exercise (Floyd's cycle detection)
  • Platform: LeetCode — https://leetcode.com/problems/linked-list-cycle/
  • Topic: linked list
  • Difficulty: Easy
  • Pattern: slow/fast pointers (Floyd's tortoise and hare)
  • Basic idea inherited from: traversal, কিন্তু দুই speed-এ একসাথে চালানো

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

একটা linked list দেওয়া। এতে কি কোনো cycle (চক্র) আছে? মানে — হাঁটতে হাঁটতে কি কখনো আগের কোনো node-এ ফিরে আসবে আর চিরকাল ঘুরতে থাকবে? True/False return করো।

উদাহরণ
cycle আছে:   1 -> 2 -> 3 -> 4
                  ^         |
                  └─────────┘     (4 আবার 2-তে ফেরে)

cycle নেই:   1 -> 2 -> 3 -> 4 -> None

Input ও output

উদাহরণ
Input : 3 -> 2 -> 0 -> -4 , শেষ node আবার 2-তে যুক্ত   -> Output: True
Input : 1 -> 2 , শেষ node আবার 1-তে যুক্ত              -> Output: True
Input : 1 -> None                                       -> Output: False
Input : None                                            -> Output: False

চেনা উদাহরণে বোঝা

গোল রানিং ট্র্যাকে দুজন দৌড়বিদ একসাথে শুরু করল — একজন আস্তে, একজন দ্বিগুণ জোরে। ট্র্যাক যদি গোল (cycle) হয়, দ্রুতজন একসময় পিছন থেকে ধীরজনকে lap দিয়ে ধরে ফেলবে। ট্র্যাক যদি সোজা হয়ে শেষ হয়ে যায় (None), তারা আর কখনো মিলবে না।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

ভিত্তি হলো সাধারণ traversal — list ধরে হাঁটা। নতুনত্ব: একটার বদলে দুটো pointer একসাথে হাঁটাই, ভিন্ন গতিতে। এই "দুই speed" idea-টাই পরে middle খোঁজা (problem 4) আর cycle-start খোঁজা (problem 11)-তে ফিরে আসবে।

ভেতরের যুক্তি

লুকানো অঙ্ক: একটা বদ্ধ বৃত্তে যদি একজন প্রতি step-এ ১ ঘর আর আরেকজন ২ ঘর এগোয়, তাহলে দ্রুতজন ধীরজনের সাথে নিশ্চিতভাবে একসময় মিলবে — কারণ প্রতি step-এ তাদের মধ্যে দূরত্ব ঠিক ১ করে কমে, তাই কখনো ০ হবেই (একে অপরকে "টপকে" যেতে পারে না)। cycle না থাকলে দ্রুতজন আগে None-এ পৌঁছে যায়।

কী দিয়ে তথ্য রাখব

দুই রকম সমাধান:

  • সহজ: একটা hash set-এ দেখা node গুলো রাখো; আবার এলে cycle।
  • সেরা: দুটো pointer (slow, fast) — কোনো extra structure ছাড়াই, O(1) space।

এটি কেন উপযুক্ত

hash set লাগলে O(n) extra memory। কিন্তু linked list-এ আমরা একই node-এ দুই গতিতে হাঁটতে পারি — তাই দুটো pointer-ই যথেষ্ট। cycle-এর ভেতরে ঢুকলে fast পিছন থেকে slow-কে ধরে ফেলে; এটা O(1) space-এ cycle ধরার নিখুঁত উপায়।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

প্রতিটা node visit করার সময় তাকে একটা set-এ রাখো। নতুন node যদি আগে থেকেই set-এ থাকে → cycle। None-এ পৌঁছালে → cycle নেই।

উদাহরণ
seen = {}
3 দেখলাম -> seen={3}
2 দেখলাম -> seen={3,2}
0 দেখলাম -> seen={3,2,0}
-4 দেখলাম -> seen={3,2,0,-4}
আবার 2 -> 2 already seen -> True

কোথায় বেশি কাজ হচ্ছে

সময় O(n) ঠিকই, কিন্তু space O(n) — সব node set-এ রাখতে হয়। বড় list-এ এটা অপচয়। দুই-pointer পদ্ধতি একই কাজ O(1) space-এ করে।

যে বিষয়টি খেয়াল করতে হবে

cycle থাকলে দ্রুত-pointer ধীর-pointer-কে ভেতরের চক্রে একসময় ধরবেই; cycle না থাকলে দ্রুত-pointer তার আগে list-এর শেষ (None) ছুঁয়ে ফেলবে। তাই "fast None ছুঁলো না slow-কে ধরল" — এই দুটোর একটা ঘটবেই।

আরও কম কাজে সমাধান

slow আর fast দুটোকেই head থেকে শুরু করো। প্রতি step-এ slow ১ ঘর, fast ২ ঘর এগোও। যদি কখনো slow is fast → cycle আছে। যদি fast (বা fast.next) None হয়ে যায় → cycle নেই।

ভাবনার পরিবর্তন

মোচড়: cycle ধরতে "কোথায় কোথায় গেছি" মনে রাখার (set) দরকার নেই — শুধু দুই গতির দুটো pointer ছাড়ো; cycle থাকলে দ্রুতজন ধীরজনকে ধরে ফেলবেই। স্মৃতির বদলে গতি।

ছবিতে বোঝা

slow ১ ঘর, fast ২ ঘর। 1→2→3→4 এবং 4.next=2 (চক্র: 2→3→4→2):

উদাহরণ
শুরু:        slow=1, fast=1
step 1:      slow=2, fast=3
step 2:      slow=3, fast=2   (fast: 3->4->2)
step 3:      slow=4, fast=4   ← slow == fast → cycle! True

cycle নেই (1->2->3->None):
step 1:      slow=2, fast=3
পরের guard: fast=3 কিন্তু fast.next=None; loop চলে না → False

ছোট input-এ ধাপে ধাপে

1 -> 2 -> 3 -> 4, আর 4.next = 2 (cycle):

  1. slow=1, fast=1
  2. slow=2, fast=3
  3. slow=3, fast=2 (fast: 3→4→2)
  4. slow=4, fast=4 → slow is fast → return True

কোড ও ব্যাখ্যা

Python

Python
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:     # fast দুই ঘর এগোবে, তাই দুটোই থাকা চাই
        slow = slow.next          # ১ ঘর
        fast = fast.next.next     # ২ ঘর
        if slow is fast:          # দেখা হয়ে গেল → cycle
            return True
    return False                  # fast None ছুঁলো → cycle নেই

# ---- helper: values + cycle position (-1 = no cycle) দিয়ে list বানাও ----
def build_with_cycle(values, pos=-1):
    nodes = [ListNode(v) for v in values]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    if pos != -1:
        nodes[-1].next = nodes[pos]   # শেষ node-কে pos-এ জুড়ে cycle বানাও
    return nodes[0] if nodes else None

# ---- tests ----
assert has_cycle(build_with_cycle([3, 2, 0, -4], pos=1)) is True
assert has_cycle(build_with_cycle([1, 2], pos=0)) is True
assert has_cycle(build_with_cycle([1], pos=-1)) is False
assert has_cycle(build_with_cycle([], pos=-1)) is False
print("সব test pass!")

কোডের প্রতিটি অংশ

  • slow = fast = head — দুজনেই head থেকে শুরু।
  • while fast and fast.next: — fast দুই ঘর লাফায়, তাই fast ও fast.next দুটোই থাকতে হবে; নাহলে list শেষ → cycle নেই।
  • slow = slow.next — ধীরজন ১ ঘর।
  • fast = fast.next.next — দ্রুতজন ২ ঘর।
  • if slow is fast: — একই node-এ মিলেছে (is = একই object, value নয়) → cycle।
  • return False — loop স্বাভাবিকভাবে শেষ মানে fast None ছুঁয়েছে → cycle নেই।

Output মিলিয়ে দেখা

[3,2,0,-4] pos=1 → 4 নম্বর node 2-তে ফেরে → True। [1,2] pos=0 → True। একক node, cycle নেই → False। খালি → False। সব assert pass → সব test pass!।

JavaScript ও test cases

JavaScript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

class ListNode {
  constructor(val = 0, next = null) { this.val = val; this.next = next; }
}
// ---- values + cycle position (-1 = no cycle) দিয়ে list বানাও ----
const buildWithCycle = (values, pos = -1) => {
  const nodes = values.map(v => new ListNode(v));
  for (let i = 0; i < nodes.length - 1; i++) nodes[i].next = nodes[i + 1];
  if (pos !== -1 && nodes.length) nodes[nodes.length - 1].next = nodes[pos]; // cycle জোড়ো
  return nodes.length ? nodes[0] : null;
};

function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {     // fast দুই ঘর এগোবে, তাই দুটোই থাকা চাই
    slow = slow.next;            // ১ ঘর
    fast = fast.next.next;       // ২ ঘর
    if (slow === fast) return true;   // দেখা হয়ে গেল -> cycle
  }
  return false;                  // fast None ছুঁলো -> cycle নেই
}

// ---- test cases ----
assert(hasCycle(buildWithCycle([3, 2, 0, -4], 1)) === true, "cycle@1");
assert(hasCycle(buildWithCycle([1, 2], 0)) === true, "cycle@0");
assert(hasCycle(buildWithCycle([1], -1)) === false, "single no cycle");
assert(hasCycle(buildWithCycle([], -1)) === false, "empty");
console.log("সব JS test pass!");

JS টীকা: node-পরিচয় তুলনায় === ব্যবহার করো (slow === fast) — এটা reference equality, মানে "একই object কি না", value নয়; তাই দুটো ভিন্ন node-এর val সমান হলেও ভুল true আসবে না। buildWithCycle helper-এ একটা node-কে অন্য node-এ next দিয়ে জুড়ে ইচ্ছাকৃত cycle বানাই — তা নাহলে node-এ cycle test করাই যেত না। while (fast && fast.next) দুটোই check করে যাতে fast.next.next-এ crash না হয়।

TypeScript ও test cases

TypeScript
interface ListNode { val: number; next: ListNode | null }

const buildWithCycle = (values: number[], pos = -1): ListNode | null => {
  const nodes: ListNode[] = values.map(v => ({ val: v, next: null }));
  for (let i = 0; i < nodes.length - 1; i++) nodes[i].next = nodes[i + 1];
  if (pos !== -1 && nodes.length) nodes[nodes.length - 1].next = nodes[pos];
  return nodes.length ? nodes[0] : null;
};

function hasCycle(head: ListNode | null): boolean {
  let slow: ListNode | null = head;
  let fast: ListNode | null = head;
  while (fast && fast.next) {
    slow = slow!.next;           // slow fast-এর পিছনে, তাই fast থাকলে slow-ও আছে
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

function expect<T>(a: T, e: T, m = ""): void { if (a !== e) throw new Error(`FAIL ${m}`); }
expect(hasCycle(buildWithCycle([3, 2, 0, -4], 1)), true, "cycle1");
expect(hasCycle(buildWithCycle([1, 2], 0)), true, "cycle0");
expect(hasCycle(buildWithCycle([1], -1)), false, "single");
expect(hasCycle(buildWithCycle([], -1)), false, "empty");
console.log("সব TS test pass!");

TS টীকা: next: ListNode | null union-ই cycle-কে type-level-এ অনুমোদন করে (একটা node-এর next আরেকটা node)। slow!.next-এ non-null assertion দিই কারণ fast non-null হলে তার পিছনের slow-ও যুক্তিগতভাবে non-null, কিন্তু কম্পাইলার সেটা নিজে বুঝতে পারে না। === দিয়ে reference তুলনা TS-এও একইভাবে কাজ করে।

খরচ ও সাধারণ ভুল

সময়

O(n) — cycle না থাকলে fast n/2 ধাপে শেষ; cycle থাকলে চক্রের ভেতরে কয়েক ধাপেই দেখা হয় — মোট রৈখিক।

অতিরিক্ত জায়গা

O(1) — শুধু দুটো pointer; hash set-এর O(n) লাগে না।

যে ভুলগুলো এড়াতে হবে

  • while শর্তে শুধু fast চেক করা, fast.next না — তখন fast.next.next-এ crash।
  • slow == fast (value তুলনা) লেখা slow is fast-এর বদলে — দুটো ভিন্ন node-এর value সমান হলে ভুল True আসতে পারে।
  • দুই pointer-কে আলাদা জায়গা থেকে শুরু করা — এখানে দুটোই head থেকে শুরু হওয়া উচিত।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি: linked list traversal (../operations.md)। দুই-speed চিন্তার ছবি ../visual-explanation.md-এর "tortoise–hare" frame-এ।

পরের অনুশীলন

কৌশলটি মনে রাখুন

Slow/fast pointers (Floyd): এক pointer ১ ঘর, আরেকটা ২ ঘর — cycle ধরা, middle খোঁজা, nth-from-end সব এই pattern-এর পরিবার।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "cycle / middle / এক-পাসে দূরত্ব — মাথায় slow ও fast দুটো pointer আনো। cycle থাকলে fast slow-কে ধরে; না থাকলে fast None-এ পড়ে।" Memory নয়, গতির খেলা।

কোথায় কাজে লাগে

  • Deadlock/loop detection: dependency graph বা resource-allocation chain-এ চক্র আছে কিনা ধরতে Floyd-জাতীয় cycle detection।
  • Memory leak / reference cycle: garbage collector ও object-graph analysis-এ circular reference খুঁজতে।
  • Linked-data integrity: corrupt/malicious linked structure-এ infinite loop থেকে বাঁচতে cycle check।
  • Functional iteration (ρ-detection): random number generator বা hashing function-এ পুনরাবৃত্তি (period) খুঁজতে — Pollard's rho-ও একই idea।
  • State-machine loops: কোনো state-transition sequence অসীম লুপে পড়ছে কিনা detect করতে।

এক কথায়, যেখানেই একটা "next" follow করে চলা যায় আর infinite loop-এর ঝুঁকি আছে, সেখানে O(1)-space slow/fast pointer cycle-detection-ই আদর্শ।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।