003 — Linked List Cycle¶

Source¶

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-এ একসাথে চালানো

1. Problem in simple words¶

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

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

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

2. Which basic idea does this inherit from?¶

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

3. What is the hidden math or logic?¶

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

4. Which data structure is needed?¶

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

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

5. Why this data structure fits¶

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

6. Real-life analogy¶

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

7. Visual explanation¶

slow ১ ঘর, fast ২ ঘর। 1->2->3->4->2... (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
step 2:      slow=3, fast=None  → fast None ছুঁলো → False

8. Example input and 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

9. Brute force thinking¶

প্রতিটা 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

10. Why brute force is slow¶

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

11. Key observation¶

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

12. Optimized intuition¶

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

13. Thinking tweak¶

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

14. Step-by-step dry run¶

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

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

15. Python solution¶

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!")

16. Line-by-line code explanation¶

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 নেই।

17. Output walkthrough¶

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

18. Time complexity¶

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

19. Space complexity¶

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

20. Common mistakes¶

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

21. Which basic problem this inherits from¶

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

22. Similar harder problems¶

Linked List Cycle II (cycle কোথায় শুরু) — https://leetcode.com/problems/linked-list-cycle-ii/ (এই tracker-এর #11)
Middle of the Linked List (একই skeleton) — https://leetcode.com/problems/middle-of-the-linked-list/ (#4)
Find the Duplicate Number (array-তে Floyd) — https://leetcode.com/problems/find-the-duplicate-number/

23. Pattern learned¶

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

24. Final summary¶

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

25. JavaScript solution (with test cases)¶

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 না হয়।

26. TypeScript solution (with test cases)¶

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-এও একইভাবে কাজ করে।

27. কোথায় কাজে লাগে (real-world use)¶

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।