لنکڈ لسٹ کے درمیانی نوڈ کو حذف کریں

𝗗𝗲𝗹𝗲𝘁𝗲 𝘁𝗵𝗲 𝗠𝗶𝗱𝗱𝗹𝗲 𝗡𝗼𝗱𝗲 𝗼𝗳 𝗮 𝗟𝗶𝗻𝗸𝗲𝗱 𝗟𝗶𝘀𝘁

آپ کو ایک سنگلی لنکڈ لسٹ (singly linked list) سے درمیانی نوڈ کو ہٹانا ہے۔ 0-بیسڈ انڈیکسنگ (0-based indexing) کا استعمال کرتے ہوئے درمیانی نوڈ ⌊n / 2⌋واں نوڈ ہے۔

اسے مؤثر طریقے سے حل کرنے کا طریقہ یہ ہے۔

The Strategy

درمیانی نوڈ کو ایک ہی بار میں تلاش کرنے کے لیے دو پوائنٹرز کا استعمال کریں۔

• ایک سلو پوائنٹر (slow pointer) استعمال کریں جو ایک وقت میں ایک قدم آگے بڑھے۔
• ایک فاسٹ پوائنٹر (fast pointer) استعمال کریں جو ایک وقت میں دو قدم آگے بڑھے۔
• جب فاسٹ پوائنٹر آخر تک پہنچ جائے گا، تو سلو پوائنٹر درمیانی مقام پر ہوگا۔
• سلو پوائنٹر سے پہلے والے نوڈ کا پتہ لگانے کے لیے ایک تیسرا پوائنٹر رکھیں۔

The Logic

1. ایج کیس (edge case) کو ہینڈل کریں۔ اگر لسٹ میں صرف ایک نوڈ ہے، تو null واپس کریں۔
2. سلو اور فاسٹ پوائنٹرز کو ہیڈ (head) پر شروع کریں۔
3. فاسٹ پوائنٹر کو دو قدم اور سلو پوائنٹر کو ایک قدم آگے بڑھائیں۔
4. ایک prev پوائنٹر کو اپ ڈیٹ کریں تاکہ وہ سلو پوائنٹر سے ایک قدم پیچھے رہے۔
5. جب لوپ ختم ہو جائے، تو prev نوڈ کو slow کے بعد والے نوڈ سے جوڑ دیں۔ اس طرح درمیانی نوڈ چھوڑ دیا جائے گا۔

Complexity

• ٹائم کمپلیکسٹی (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