কনটেন্টে যান

005 — Linked List Cycle

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

  • 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 — এখানে মেশে 03 linked lists (node-এর next ধরে ধরে হাঁটা, কিন্তু এখানে list শেষ নাও হতে পারে) আর 02 two-pointer thinking (একই sequence-এ দুটো আলাদা গতির আঙুল চালানো)। দুই tool জোড়া লাগলেই Floyd।

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

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

একটা 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

Input ও 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

উদাহরণ
seen = set()
while node:
    if node in seen: return True
    seen.add(node)
    node = node.next
return False

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

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

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

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

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

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

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

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

ছবিতে বোঝা

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

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

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)

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

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 প্রান্তে পৌঁছেছে -> 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!")

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

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

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

[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!।

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

সময়

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

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

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

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

  • 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-এ গোনে।

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

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

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

পরের অনুশীলন

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

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

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

ভবিষ্যতের আমাকে: 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।