ফ্লয়েডের লিংকড লিস্ট সাইকেল ফাইন্ডিং অ্যালগরিদম#

একটি লিংকড লিস্ট দেওয়া আছে যেখানে সেই লিংকড লিস্টের শুরুর বিন্দু head দ্বারা চিহ্নিত, এবং সেখানে সাইকেল থাকতেও পারে, নাও থাকতে পারে। উদাহরণস্বরূপ:

এখানে আমাদের C বিন্দুটি খুঁজে বের করতে হবে, অর্থাৎ সাইকেলের শুরুর বিন্দু।

প্রস্তাবিত অ্যালগরিদম#

এই অ্যালগরিদমটিকে ফ্লয়েডের সাইকেল অ্যালগরিদম বা টর্টয়েজ অ্যান্ড হেয়ার অ্যালগরিদম বলা হয়। সাইকেলের শুরুর বিন্দু খুঁজে বের করতে, আমাদের প্রথমে জানতে হবে সাইকেল আদৌ বিদ্যমান কি না। এতে দুটি ধাপ জড়িত: ১. সাইকেলের উপস্থিতি নির্ণয় করা। ২. সাইকেলের শুরুর বিন্দু খুঁজে বের করা।

ধাপ ১: সাইকেলের উপস্থিতি#

১. দুটি পয়েন্টার $slow$ এবং $fast$ নিন। ২. উভয়ই প্রাথমিকভাবে লিংকড লিস্টের head-এ পয়েন্ট করবে। ৩. $slow$ একবারে একটি ধাপ এগোবে। ৪. $fast$ একবারে দুটি ধাপ এগোবে ($slow$ পয়েন্টারের দ্বিগুণ গতিতে)। ৫. কোনো একটি (বা উভয়) null-এ পৌঁছানোর আগে কোনো সময়ে তারা একই নোডে পয়েন্ট করে কি না তা পরীক্ষা করুন। ৬. যদি তাদের যাত্রার কোনো সময়ে তারা একই নোডে পয়েন্ট করে, তাহলে এটি নির্দেশ করে যে লিংকড লিস্টে প্রকৃতপক্ষে একটি সাইকেল বিদ্যমান। ৭. যদি আমরা null পাই, তাহলে এটি নির্দেশ করে যে লিংকড লিস্টে কোনো সাইকেল নেই।

এখন, আমরা নির্ণয় করেছি যে লিংকড লিস্টে সাইকেল আছে কি না, পরবর্তী ধাপে আমাদের সাইকেলের শুরুর বিন্দু, অর্থাৎ C খুঁজে বের করতে হবে।

ধাপ ২: সাইকেলের শুরুর বিন্দু#

১. $slow$ পয়েন্টারকে লিংকড লিস্টের head-এ রিসেট করুন। ২. উভয় পয়েন্টারকে একবারে একটি ধাপ করে এগোন। ৩. যে বিন্দুতে তারা মিলিত হবে সেটিই হবে সাইকেলের শুরুর বিন্দু।

// Presence of cycle
public boolean hasCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;

    while(fast != null && fast.next != null){
        slow = slow.next;
        fast = fast.next.next;
        if(slow==fast){
            return true;
        }
    }

    return false;
}
// Assuming there is a cycle present and slow and fast are point to their meeting point
slow = head;
while(slow!=fast){
	slow = slow.next;
	fast = fast.next;
}

return slow; // the starting point of the cycle.

এটি কেন কাজ করে#

ধাপ ১: সাইকেলের উপস্থিতি#

যেহেতু পয়েন্টার $fast$, $slow$-এর দ্বিগুণ গতিতে চলছে, আমরা বলতে পারি যে যেকোনো সময়ে, $fast$ $slow$-এর দ্বিগুণ দূরত্ব অতিক্রম করেছে। আমরা আরও বলতে পারি যে এই দুটি পয়েন্টারের অতিক্রান্ত দূরত্বের পার্থক্য ১ করে বাড়ছে।

slow: 0 --> 1 --> 2 --> 3 --> 4 (distance covered)
fast: 0 --> 2 --> 4 --> 6 --> 8 (distance covered)
diff: 0 --> 1 --> 2 --> 3 --> 4 (difference between distance covered by both pointers)

ধরি $L$ সাইকেলের দৈর্ঘ্য চিহ্নিত করে, এবং $a$ slow পয়েন্টারের সাইকেলের প্রবেশবিন্দুতে পৌঁছাতে প্রয়োজনীয় ধাপের সংখ্যা উপস্থাপন করে। এমন একটি ধনাত্মক পূর্ণসংখ্যা $k$ ($k > 0$) বিদ্যমান যেন $k \cdot L \geq a$। যখন slow পয়েন্টার $k \cdot L$ ধাপ চলেছে, এবং fast পয়েন্টার $2 \cdot k \cdot L$ ধাপ অতিক্রম করেছে, উভয় পয়েন্টারই সাইকেলের মধ্যে থাকে। এই সময়ে, তাদের মধ্যে $k \cdot L$ দূরত্ব আছে। যেহেতু সাইকেলের দৈর্ঘ্য $L$ থাকে, এটি নির্দেশ করে যে তারা সাইকেলের মধ্যে একই বিন্দুতে মিলিত হয়, ফলে তাদের সাক্ষাৎ ঘটে।

ধাপ ২: সাইকেলের শুরুর বিন্দু#

সাইকেলের মধ্যে মিলিত হওয়ার বিন্দু পর্যন্ত উভয় পয়েন্টারের অতিক্রান্ত দূরত্ব হিসাব করার চেষ্টা করি।

$slowDist = a + xL + b$ , $x\ge0$

$fastDist = a + yL + b$ , $y\ge0$

  • $slowDist$ হলো slow পয়েন্টারের মোট অতিক্রান্ত দূরত্ব।
  • $fastDist$ হলো fast পয়েন্টারের মোট অতিক্রান্ত দূরত্ব।
  • $a$ হলো উভয় পয়েন্টারের সাইকেলে প্রবেশ করতে প্রয়োজনীয় ধাপের সংখ্যা।
  • $b$ হলো C এবং G-এর মধ্যবর্তী দূরত্ব, অর্থাৎ সাইকেলের শুরুর বিন্দু এবং উভয় পয়েন্টারের মিলন বিন্দুর মধ্যবর্তী দূরত্ব।
  • $x$ হলো slow পয়েন্টার সাইকেলের মধ্যে কতবার লুপ করেছে তার সংখ্যা, C থেকে শুরু করে C-তে শেষ করে।
  • $y$ হলো fast পয়েন্টার সাইকেলের মধ্যে কতবার লুপ করেছে তার সংখ্যা, C থেকে শুরু করে C-তে শেষ করে।

$fastDist = 2 \cdot (slowDist)$

$a + yL + b = 2(a + xL + b)$

সূত্রটি সমাধান করলে পাই:

$a=(y-2x)L-b$

যেখানে $y-2x$ একটি পূর্ণসংখ্যা

এর মানে মূলত এই যে $a$ ধাপ চলা হলো সাইকেলে কিছু সংখ্যক পূর্ণ লুপ করা এবং $b$ ধাপ পেছনে যাওয়ার সমান। যেহেতু fast পয়েন্টার ইতোমধ্যেই সাইকেলের প্রবেশবিন্দু থেকে $b$ ধাপ এগিয়ে আছে, fast পয়েন্টার আরও $a$ ধাপ চললে সে সাইকেলের প্রবেশবিন্দুতে পৌঁছাবে। এবং যেহেতু আমরা slow পয়েন্টারকে লিংকড লিস্টের শুরুতে রাখি, $a$ ধাপ পর এটিও সাইকেলের প্রবেশবিন্দুতে পৌঁছাবে। সুতরাং, যদি তারা উভয়ই $a$ ধাপ চলে তাহলে তারা উভয়ই সাইকেলের প্রবেশবিন্দুতে মিলিত হবে।

সমস্যাসমূহ:#