Skip to content

005 — Linked List Cycle

Source

  • Original source: Classic capstone interview problem (Floyd's tortoise and hare)
  • Platform: LeetCode — https://leetcode.com/problems/linked-list-cycle/
  • Topic: linked lists + two-pointer technique
  • Difficulty: Easy
  • Pattern: Slow/fast pointers (Floyd's cycle detection)
  • Basic idea inherited from: এটা একটা cross-topic capstone — এখানে মেশে 04 linked lists (node-এর next ধরে ধরে হাঁটা, কিন্তু এখানে list শেষ নাও হতে পারে) আর 02 two-pointer thinking (একই sequence-এ দুটো আলাদা গতির আঙুল চালানো)। দুই tool জোড়া লাগলেই Floyd।

1. Problem in simple words

একটা singly linked list দেওয়া। কখনো কখনো শেষ node None-এ না গিয়ে আগের কোনো node-এ ফিরে তাকায় — তখন list-এ একটা চক্র (cycle) তৈরি হয়, আর হাঁটতে থাকলে তুমি ঘুরতেই থাকবে, কখনো থামবে না। তোমার কাজ: শুধু বলো list-এ cycle আছে কি নেই — True বা False। (cycle কোথায় শুরু, সেটা এখানে চাওয়া হয়নি।)

cycle আছে:  1 -> 2 -> 3 -> 4
                      ^         |
                      +----<----+      (4 আবার 2-এ ফিরে গেছে)

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

2. Which basic idea does this inherit from?

এই problem দুটো আগের chapter-এর tool জোড়া দেয়:

  • 04 linked lists থেকে: next arrow ধরে হাঁটা — কিন্তু এখানে মোচড় হলো list শেষ নাও হতে পারে, তাই সাধারণ traversal আটকে যায়।
  • 02 two-pointer thinking থেকে: একই sequence-এ দুটো pointer, আলাদা গতিতে — একটা ধীর (এক ঘর), একটা দ্রুত (দুই ঘর)।

একা list-traversal cycle-এ অসীম লুপে পড়ে; একা two-pointer idea দেয় গতি-পার্থক্যের কৌশল। দুটো মিললে O(1) space-এ cycle ধরা।

3. What is the hidden math or logic?

লুকানো logic একটা relative-speed argument: দুটো pointer যদি একই cycle-এ থাকে আর প্রতি step-এ একটা অন্যটার চেয়ে ঠিক 1 ঘর এগিয়ে যায়, তাহলে তাদের মধ্যেকার দূরত্ব প্রতি step-এ 1 করে কমে — তাই দ্রুতটা ধীরটাকে অবশ্যই ধরে ফেলবে (গ্যাপ শেষে 0 হবে)। cycle না থাকলে দ্রুত pointer None-এ গিয়ে পড়ে, লুপ থামে। এটাই Floyd-এর গণিত।

4. Which data structure is needed?

কোনো extra data structure লাগে না — শুধু দুটো pointer (slow, fast)। (একটা সহজ বিকল্প: দেখা node গুলো একটা set-এ রাখা, কিন্তু সেটা O(n) space; Floyd O(1) space-এ একই কাজ করে — এটাই 02 two-pointer-এর জিত।)

5. Why this data structure fits

Linked list-এ আমরা শুধু next ধরে সামনে যেতে পারি, পিছনে না — তাই "আগে কোথায় ছিলাম" মনে রাখা কঠিন। দুটো ভিন্ন-গতির pointer এই সীমাবদ্ধতাকেই কাজে লাগায়: extra memory-তে history না রেখে, শুধু গতির পার্থক্য দিয়ে cycle ধরা পড়ে। এজন্যই two-pointer (02) linked list (04)-এর সাথে এখানে নিখুঁত খাপ খায়।

6. Real-life analogy

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

7. Visual explanation

1 -> 2 -> 3 -> 4 -> 2(4 ফিরে 2-এ) — slow এক ঘর, fast দুই ঘর:

শুরু:   slow=1   fast=1
step1:  slow=2   fast=3
step2:  slow=3   fast=2      (fast ঘুরে এসেছে)
step3:  slow=4   fast=4      <- slow == fast, cycle ধরা পড়ল!

cycle না থাকলে fast একসময় None-এ পড়ত আর লুপ থামত -> False

8. Example input and output

Input : 3 -> 2 -> 0 -> -4, শেষ node ফিরে index 1 (value 2)-এ  -> Output: True
Input : 1 -> 2, শেষ node ফিরে index 0-এ                       -> Output: True

Edge case 1 (খালি list): Input: None        -> Output: False
Edge case 2 (একটা node, cycle নেই): Input: 1 -> None -> Output: False
Edge case 3 (একটা node নিজের দিকে): Input: 1 -> 1(self) -> Output: True

9. Brute force thinking

প্রথম সরল চিন্তা: যত node দেখি, প্রতিটার পরিচয় একটা set-এ রাখি; হাঁটতে হাঁটতে যদি আগে-দেখা কোনো node-এ আবার পৌঁছাই, তাহলে cycle আছে।

seen = set()
while node:
    if node in seen: return True
    seen.add(node)
    node = node.next
return False

10. Why brute force is slow

সময় O(n) ঠিকই, কিন্তু এটা O(n) extra space নেয় — প্রতিটা node-এর reference set-এ জমে। Interview-র আসল চ্যালেঞ্জ O(1) space-এ cycle ধরা, কোনো extra memory ছাড়া। ঠিক এই জায়গায় two-pointer (02) আসে: history না রেখেও গতি-পার্থক্য দিয়ে একই কাজ।

11. Key observation

মূল observation: দুটো pointer ভিন্ন গতিতে চললে, cycle থাকলে তারা একসময় একই node-এ মিলবেই; cycle না থাকলে দ্রুতটা None-এ পড়বে। তাই দেখা-node মনে রাখার দরকার নেই — শুধু "তারা কি মিলল?" দেখলেই হয়। এটাই O(1) space এনে দেয়।

12. Optimized intuition

slow আর fast দুটোই head থেকে শুরু করো। প্রতি ধাপে slow এক ঘর, fast দুই ঘর এগোয়। যদি কখনো slow == fast হয় → cycle আছে (True)। যদি fast বা fast.next None হয়ে যায় → সোজা প্রান্ত পেয়ে গেছ, cycle নেই (False)।

13. Thinking tweak

মোচড়: "কোন node আগে দেখেছি মনে রাখব" ভাবার বদলে ভাবো "দুটো ভিন্ন-গতির আঙুল চালাই — মিললে চক্র, একজন প্রান্তে পৌঁছালে সোজা।" memory-র জায়গায় গতির পার্থক্য কাজ করে।

14. Step-by-step dry run

Input 1 -> 2 -> 3 -> 1(3 ফিরে 1-এ):

  1. শুরু: slow=1, fast=1
  2. step: slow=2, fast=3
  3. step: slow=3, fast=2 (fast 1-এ গিয়ে আবার 2)
  4. step: slow=1, fast=1... আসলে এর আগেই: slow=3 -> 1, fast=2 -> 3 -> 1; slow == fast == 1 → return True

(cycle না থাকলে কোনো এক step-এ fast বা fast.next None হতো, return False)

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 প্রান্তে পৌঁছেছে -> cycle নেই

# ---- helpers (test-এর জন্য) ----
def build_with_cycle(values, pos):
    # pos = -1 হলে cycle নেই; নাহলে শেষ node index pos-এ ফিরে তাকায়
    if not values:
        return None
    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]
    return nodes[0]

# ---- tests ----
assert has_cycle(build_with_cycle([3, 2, 0, -4], 1)) is True   # 4 -> 2
assert has_cycle(build_with_cycle([1, 2], 0)) is True          # 2 -> 1
assert has_cycle(build_with_cycle([1, 2, 3], -1)) is False     # সোজা list
assert has_cycle(build_with_cycle([], -1)) is False            # খালি
assert has_cycle(build_with_cycle([1], -1)) is False           # একক, cycle নেই
assert has_cycle(build_with_cycle([1], 0)) is True             # একক, নিজের দিকে
print("সব test pass!")

16. Line-by-line code explanation

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

17. Output walkthrough

[3,2,0,-4] (4 ফিরে 2-এ): slow/fast কয়েক ধাপে cycle-এর ভেতর একই node-এ মেলে → True — assert pass। [1,2,3] সোজা list-এ fast শেষে None-এ পড়ে → False। খালি ও একক-node case-ও সঠিক; একক node নিজের দিকে তাকালে এক ধাপেই slow is fast → True। শেষে print: সব test pass!।

18. Time complexity

O(n) — cycle না থাকলে fast ~n/2 ধাপে প্রান্তে; cycle থাকলে দুজনে cycle-দৈর্ঘ্যের মধ্যে মেলে — মোট রৈখিক।

19. Space complexity

O(1) — শুধু দুটো pointer; দেখা node মনে রাখার set লাগে না (এটাই brute force-এর উপর Floyd-এর জিত)।

20. Common mistakes

  • while শর্তে শুধু fast দেখা (fast.next বাদ) — তখন fast.next.next-এ None.next crash করবে।
  • slow == fast (value সমতা) লেখা slow is fast-এর বদলে — ভিন্ন node-এর value এক হলে ভুল True দিতে পারে; identity (is) চাই।
  • খালি list / একক node আলাদা করে না ভাবা — যদিও while শর্ত এমনিতেই এদের সামলায়, মুখে edge case বলা rubric-এ গোনে।

21. Which basic problem this inherits from

ভিত্তি: linked list traversal (04-এর ../../04-linked-lists/) + একই sequence-এ দুই-গতির pointer চালানো (02 two-pointer, ../../02-arrays-and-strings/)। "find the middle of a list" (slow/fast)-ও ঠিক একই কৌশলের ভাই।

22. Similar harder problems

23. Pattern learned

Slow/fast pointers (Floyd): একই sequence-এ এক-ঘর ও দুই-ঘর গতির দুই pointer চালিয়ে, "মিললে cycle, প্রান্তে পৌঁছালে নেই" — O(1) space-এ cycle detection। middle-finding আর duplicate-finding-এও একই engine।

24. Final summary

ভবিষ্যতের আমাকে: linked list-এ "cycle আছে কি না" বা "middle কোথায়" শুনলেই slow/fast pointer মনে করবে। মূল কথা — set-এ history রাখার দরকার নেই, গতির পার্থক্যই কাজ করে; আর is দিয়ে identity মেলাও, value না। while fast and fast.next শর্তটা মুখস্থ রাখা চাই, এটাই crash ঠেকায়।

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