একটি লিঙ্কড লিস্টের মাঝের নোডটি মুছে ফেলুন
আপনাকে একটি সিঙ্গলি লিঙ্কড লিস্ট থেকে মাঝের নোডটি সরিয়ে ফেলতে হবে। ০-ভিত্তিক ইনডেক্সিং অনুযায়ী মাঝের নোডটি হলো ⌊n / 2⌋-তম নোড।
নিচে এটি দক্ষতার সাথে সমাধান করার পদ্ধতি দেওয়া হলো।
কৌশল
একবার লিস্টটি ট্রাভার্স করেই মাঝের নোডটি খুঁজে পেতে দুটি পয়েন্টার ব্যবহার করুন।
- একটি স্লো (slow) পয়েন্টার ব্যবহার করুন যা প্রতিবার এক ধাপ করে এগোবে।
- একটি ফাস্ট (fast) পয়েন্টার ব্যবহার করুন যা প্রতিবার দুই ধাপ করে এগোবে।
- যখন ফাস্ট পয়েন্টারটি শেষ প্রান্তে পৌঁছাবে, স্লো পয়েন্টারটি মাঝের নোডে অবস্থান করবে।
- স্লো পয়েন্টারের আগের নোডটি ট্র্যাক করার জন্য একটি তৃতীয় পয়েন্টার রাখুন।
লজিক
- এজ কেস (edge case) হ্যান্ডেল করুন। যদি লিস্টে মাত্র একটি নোড থাকে, তবে null রিটার্ন করুন।
- হেড (head)-এ স্লো এবং ফাস্ট পয়েন্টার দুটি ইনিশিয়ালাইজ করুন।
- ফাস্ট পয়েন্টারকে দুই ধাপ এবং স্লো পয়েন্টারকে এক ধাপ করে মুভ করুন।
- স্লো পয়েন্টারের ঠিক এক ধাপ পেছনে থাকার জন্য একটি prev পয়েন্টার আপডেট করুন।
- লুপ শেষ হলে, prev নোডটিকে slow-এর পরের নোডের সাথে লিঙ্ক করে দিন। এতে মাঝের নোডটি বাদ পড়ে যাবে।
কমপ্লেক্সিটি
- Time Complexity: O(n)। আপনি লিস্টটি একবার ট্রাভার্স করছেন।
- Space Complexity: O(1)। আপনি মাত্র তিনটি পয়েন্টার ব্যবহার করছেন।
PHP Implementation
function deleteMiddle(ListNode $head): ?ListNode
{
if ($head->next == null) {
return null;
}
$slow = $head;
$fast = $head;
$prev = null;
while ($fast !== null && $fast->next !== null) {
$prev = $slow;
$slow = $slow->next;
$fast = $fast->next->next;
}
$prev->next = $slow->next;
return $head;
}
Source: https://dev.to/mdarifulhaque/2095-delete-the-middle-node-of-a-linked-list-4jf1