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

ਇੱਕ Linked List ਦੇ ਵਿਚਕਾਰਲੇ ਨੋਡ (Middle Node) ਨੂੰ ਡਿਲੀਟ ਕਰੋ

ਤੁਹਾਨੂੰ ਇੱਕ singly linked list ਵਿੱਚੋਂ ਵਿਚਕਾਰਲੇ ਨੋਡ ਨੂੰ ਹਟਾਉਣ ਦੀ ਲੋੜ ਹੈ। 0-ਅਧਾਰਤ ਇੰਡੈਕਸਿੰਗ (0-based indexing) ਦੀ ਵਰਤੋਂ ਕਰਦੇ ਹੋਏ, ਵਿਚਕਾਰਲਾ ਨੋਡ ⌊n / 2⌋-ਵਾਂ ਨੋਡ ਹੁੰਦਾ ਹੈ।

ਇੱਥੇ ਇਸਨੂੰ ਕੁਸ਼ਲਤਾ ਨਾਲ ਹੱਲ ਕਰਨ ਦਾ ਤਰੀਕਾ ਦਿੱਤਾ ਗਿਆ ਹੈ।

ਰਣਨੀਤੀ (The Strategy)

ਇੱਕ ਹੀ ਪਾਸ (one pass) ਵਿੱਚ ਵਿਚਕਾਰਲਾ ਨੋਡ ਲੱਭਣ ਲਈ ਦੋ ਪੁਆਇੰਟਰਾਂ (pointers) ਦੀ ਵਰਤੋਂ ਕਰੋ।

• ਇੱਕ slow pointer ਦੀ ਵਰਤੋਂ ਕਰੋ ਜੋ ਇੱਕ ਵਾਰ ਵਿੱਚ ਇੱਕ ਕਦਮ ਚੱਲਦਾ ਹੈ।
• ਇੱਕ fast pointer ਦੀ ਵਰਤੋਂ ਕਰੋ ਜੋ ਇੱਕ ਵਾਰ ਵਿੱਚ ਦੋ ਕਦਮ ਚੱਲਦਾ ਹੈ।
• ਜਦੋਂ fast pointer ਅੰਤ ਤੱਕ ਪਹੁੰਚ ਜਾਂਦਾ ਹੈ, ਤਾਂ slow pointer ਵਿਚਕਾਰਲੇ ਨੋਡ 'ਤੇ ਹੁੰਦਾ ਹੈ।
• slow pointer ਤੋਂ ਪਹਿਲਾਂ ਵਾਲੇ ਨੋਡ ਨੂੰ ਟ੍ਰੈਕ ਕਰਨ ਲਈ ਇੱਕ ਤੀਜਾ ਪੁਆਇੰਟਰ ਰੱਖੋ।

ਤਰਕ (The Logic)

1. ਐਜ ਕੇਸ (edge case) ਨੂੰ ਸੰਭਾਲੋ। ਜੇਕਰ ਲਿਸਟ ਵਿੱਚ ਸਿਰਫ਼ ਇੱਕ ਨੋਡ ਹੈ, ਤਾਂ null ਰਿਟਰਨ ਕਰੋ।
2. slow ਅਤੇ fast ਪੁਆਇੰਟਰਾਂ ਨੂੰ head 'ਤੇ ਇਨੀਸ਼ੀਅਲਾਈਜ਼ (initialize) ਕਰੋ।
3. fast pointer ਨੂੰ ਦੋ ਕਦਮ ਅਤੇ slow pointer ਨੂੰ ਇੱਕ ਕਦਮ ਚਲਾਓ।
4. slow pointer ਤੋਂ ਇੱਕ ਕਦਮ ਪਿੱਛੇ ਰਹਿਣ ਲਈ ਇੱਕ prev ਪੁਆਇੰਟਰ ਨੂੰ ਅਪਡੇਟ ਕਰੋ।
5. ਜਦੋਂ ਲੂਪ ਖਤਮ ਹੋ ਜਾਂਦਾ ਹੈ, ਤਾਂ prev ਨੋਡ ਨੂੰ slow ਤੋਂ ਬਾਅਦ ਵਾਲੇ ਨੋਡ ਨਾਲ ਜੋੜ ਦਿਓ। ਇਹ ਵਿਚਕਾਰਲੇ ਨੋਡ ਨੂੰ ਛੱਡ ਦੇਵੇਗਾ।

ਜਟਿਲਤਾ (Complexity)

• Time Complexity: O(n)। ਤੁਸੀਂ ਲਿਸਟ ਰਾਹੀਂ ਇੱਕ ਵਾਰ ਗੁਜ਼ਰਦੇ ਹੋ।
• Space Complexity: O(1)। ਤੁਸੀਂ ਸਿਰਫ਼ ਤਿੰਨ ਪੁਆਇੰਟਰਾਂ ਦੀ ਵਰਤੋਂ ਕਰਦੇ ਹੋ।

PHP ਇੰਪਲੀਮੈਂਟੇਸ਼ਨ (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;
}

ਸਰੋਤ: https://dev.to/mdarifulhaque/2095-delete-the-middle-node-of-a-linked-list-4jf1