Skip to content

011 — Linked List Cycle II

Source

  • Original source: Classic linked list exercise (Floyd's cycle detection, phase 2)
  • Platform: LeetCode — https://leetcode.com/problems/linked-list-cycle-ii/
  • Topic: linked list
  • Difficulty: Medium
  • Pattern: Floyd's phase 2 (slow/fast meet, তারপর head থেকে আবার)
  • Basic idea inherited from: cycle detection (problem 3) + distance algebra

1. Problem in simple words

একটা linked list-এ যদি cycle (চক্র) থাকে, তাহলে সেই চক্রটা কোন node থেকে শুরু হয়েছে সেই node-টা return করো। cycle না থাকলে None return করো।

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

cycle শুরু = node 2

2. Which basic idea does this inherit from?

এটা সরাসরি problem 3 (003-linked-list-cycle.md)-এর উপর দাঁড়িয়ে। সেখানে শুধু "cycle আছে কি না" ধরা হয়েছিল slow/fast দিয়ে। এখানে এক ধাপ এগিয়ে — কোথায় শুরু সেটা বের করা। নতুন উপাদান একটা সুন্দর distance algebra (দূরত্বের অঙ্ক), যা phase 2-তে কাজে লাগে।

3. What is the hidden math or logic?

ধরা যাক head থেকে cycle-শুরু পর্যন্ত দূরত্ব a, cycle-শুরু থেকে দেখা-হওয়ার বিন্দু পর্যন্ত b, আর চক্রের দৈর্ঘ্য c। দেখা হওয়ার সময় slow গেছে a + b, fast গেছে a + b + k·c (k বার চক্র ঘুরে)। fast দ্বিগুণ গতির, তাই 2(a + b) = a + b + k·c, অর্থাৎ a + b = k·c, মানে a = k·c − b = (k−1)·c + (c − b)। ফলাফল: দেখা-বিন্দু থেকে আর head থেকে — দুজন একই গতিতে হাঁটলে তারা ঠিক cycle-শুরুতে মিলবে।

4. Which data structure is needed?

কোনো extra structure নয় — শুধু দুটো pointer। প্রথম পর্বে slow/fast দিয়ে দেখা-বিন্দু খুঁজি; দ্বিতীয় পর্বে একটাকে head-এ ফিরিয়ে দুজনকে এক গতিতে হাঁটাই। O(1) space।

5. Why this data structure fits

cycle-শুরু খুঁজতে hash set-এ সব node রাখলে O(n) memory লাগত। কিন্তু উপরের distance algebra বলছে শুধু দুটো pointer-এর গতি নিয়ন্ত্রণ করেই উত্তর পাওয়া যায়। linked list-এ একই node-এ দুই গতিতে হাঁটা যায় বলেই এই অঙ্ক খাটে — তাই O(1) space-এই কাজ হয়।

6. Real-life analogy

গোল ট্র্যাকে দুজন দৌড়বিদ — একজন দ্বিগুণ জোরে — কোথাও একটা lap-এ মিলল (phase 1)। এবার একজন আবার শুরুর গেটে ফিরে গিয়ে দুজনে একই গতিতে হাঁটল; অঙ্কের নিয়মে তারা ঠিক সেই জায়গায় মিলবে যেখানে সোজা রাস্তা ট্র্যাকের গোল অংশে ঢুকেছে — অর্থাৎ চক্রের প্রবেশমুখ।

7. Visual explanation

দুই পর্ব। 1->2->3->4, 4 ফেরে 2-তে (cycle শুরু = 2):

phase 1 (slow 1 ঘর, fast 2 ঘর — দেখা হওয়া পর্যন্ত):
    slow=1, fast=1
    slow=2, fast=3
    slow=3, fast=2   (fast: 3->4->2)
    slow=4, fast=4   ← দেখা! meeting = node 4

phase 2 (একটা head-এ, দুজনে 1 ঘর করে):
    ptr=1 , slow=4
    ptr=2 , slow=2   ← মিলল! cycle শুরু = node 2

8. Example input and output

Input : 3 -> 2 -> 0 -> -4 , শেষ node 2-তে ফেরে   -> Output: node 2 (index 1)
Input : 1 -> 2 , শেষ node 1-তে ফেরে               -> Output: node 1 (index 0)
Input : 1 -> 2 -> 3 (cycle নেই)                    -> Output: None
Input : 1 (cycle নেই)                              -> Output: None

9. Brute force thinking

সরল চিন্তা: হাঁটতে হাঁটতে প্রতিটা node একটা set-এ রাখো। যেই প্রথম node আবার set-এ পাওয়া যাবে, সেটাই cycle-শুরু — সেটা return করো। None-এ পৌঁছালে cycle নেই।

seen = {}
3 দেখলাম -> {3}
2 দেখলাম -> {3,2}
0 দেখলাম -> {3,2,0}
-4 দেখলাম -> {3,2,0,-4}
আবার 2 -> 2 already seen -> cycle শুরু = node 2

10. Why brute force is slow

সময় O(n) ঠিকই, কিন্তু space O(n) — প্রতিটা node set-এ রাখতে হয়। Floyd-এর দুই-pointer পদ্ধতি একই উত্তর O(1) space-এ দেয়, কোনো node মনে না রেখেই — শুধু গতির অঙ্কে।

11. Key observation

মূল observation: phase 1-এ দেখা-হওয়ার বিন্দু থেকে আর head থেকে — এই দুই বিন্দু cycle-শুরু থেকে সমান দূরত্বে (mod চক্র-দৈর্ঘ্য)। তাই দুজনকে এক গতিতে হাঁটালে তারা ঠিক প্রবেশমুখে মিলবে।

12. Optimized intuition

প্রথমে problem 3-এর মতো slow/fast চালাও; slow is fast হলে cycle আছে, ওই বিন্দু ধরে রাখো। যদি fast None ছোঁয় — cycle নেই, None। cycle থাকলে একটা pointer head-এ ফিরিয়ে দাও, তারপর দুজনকে এক ঘর করে একসাথে এগোও; যেখানে মিলবে, সেটাই cycle-শুরু।

13. Thinking tweak

মোচড়: "কোথায় কোথায় গেছি মনে রাখব" (set) না ভেবে ভাবো — "দেখা হয়ে গেলে একজনকে শুরুতে ফেরত পাঠাই; এবার দুজনে সমান কদমে হাঁটলে অঙ্ক নিজেই প্রবেশমুখে মিলিয়ে দেবে।" স্মৃতির বদলে দূরত্বের সমীকরণ।

14. Step-by-step dry run

1 -> 2 -> 3 -> 4, 4.next = 2 (cycle শুরু = node 2):

  1. phase 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 → দেখা-বিন্দু = node 4
  5. phase 2: ptr=head=1, slow=4
  6. ptr != slow → ptr=2, slow=2 (4→2)
  7. ptr is slow (node 2) → return node 2

15. Python solution

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

def detect_cycle(head):
    slow = fast = head
    while fast and fast.next:        # phase 1: দেখা-বিন্দু খোঁজা
        slow = slow.next             # 1 ঘর
        fast = fast.next.next        # 2 ঘর
        if slow is fast:             # দেখা হয়ে গেল
            ptr = head               # phase 2: একজন head-এ
            while ptr is not slow:   # দুজনে এক ঘর করে
                ptr = ptr.next
                slow = slow.next
            return ptr               # মিলন-বিন্দু = cycle শুরু
    return None                      # fast None ছুঁলো → cycle নেই

# ---- helper: cycle-সহ list বানাও, সব node-এর তালিকা ফেরাও ----
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

# ---- tests (identity দিয়ে যাচাই, value নয়) ----
nodes = build_with_cycle([3, 2, 0, -4], pos=1)
assert detect_cycle(nodes[0]) is nodes[1]      # cycle শুরু = index 1

nodes = build_with_cycle([1, 2], pos=0)
assert detect_cycle(nodes[0]) is nodes[0]      # cycle শুরু = index 0

nodes = build_with_cycle([1, 2, 3], pos=-1)
assert detect_cycle(nodes[0]) is None          # cycle নেই

nodes = build_with_cycle([1], pos=-1)
assert detect_cycle(nodes[0]) is None          # একক node, cycle নেই

assert detect_cycle(None) is None              # খালি
print("সব test pass!")

16. Line-by-line code explanation

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

17. Output walkthrough

[3,2,0,-4] pos=1: phase 1-এ দেখা হয়, phase 2-তে head ও মিলন-বিন্দু এক গতিতে এগিয়ে index 1-এ মেলে → nodes[1]। [1,2] pos=0 → nodes[0]। cycle না থাকলে fast None ছোঁয় → None। একক node ও খালি → None। সব assert pass → সব test pass!।

18. Time complexity

O(n) — phase 1-এ দেখা হতে রৈখিক ধাপ; phase 2-তে head থেকে প্রবেশমুখ পর্যন্ত আরও রৈখিক — মোট O(n)।

19. Space complexity

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

20. Common mistakes

  • phase 2-তে দুজনকেই দ্বিগুণ গতিতে চালানো — দুজনেই এক ঘর করে এগোতে হবে।
  • দেখা-বিন্দু পাওয়ার পর সেখান থেকেই দুজনকে চালানো (একজনকে head-এ ফেরত না পাঠানো)।
  • slow == fast (value তুলনা) লেখা slow is fast-এর বদলে — ভিন্ন node-এর value সমান হলে ভুল হতে পারে।
  • while fast শর্তে fast.next বাদ দেওয়া — fast.next.next-এ crash।

21. Which basic problem this inherits from

ভিত্তি: problem 3 (003-linked-list-cycle.md)-এর slow/fast cycle detection; তার উপর distance algebra বসিয়ে cycle-শুরু বের করা। দুই-speed চিন্তার ছবি ../visual-explanation.md-এর "tortoise–hare" frame-এ।

22. Similar harder problems

23. Pattern learned

Floyd's phase 2: slow/fast দিয়ে দেখা-বিন্দু পাও, তারপর একটা pointer head-এ ফিরিয়ে দুজনকে এক গতিতে হাঁটাও — মিলন-বিন্দুই cycle-শুরু; পুরোটা O(1) space-এ।

24. Final summary

ভবিষ্যতের আমাকে: "cycle কোথায় শুরু? আগে slow/fast দিয়ে দেখা করাও; তারপর একজনকে head-এ ফেরত পাঠিয়ে দুজনে সমান কদমে হাঁটাও — যেখানে মেলে, ওটাই প্রবেশমুখ।" a = k·c − b অঙ্কটাই এর প্রাণ।

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