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

ഒരു ലിങ്ക്ഡ് ലിസ്റ്റിലെ മധ്യഭാഗത്തെ നോഡ് നീക്കം ചെയ്യുക

ഒരു സിംഗ്ലി ലിങ്ക്ഡ് ലിസ്റ്റിൽ (singly linked list) നിന്ന് മധ്യഭാഗത്തെ നോഡ് നീക്കം ചെയ്യേണ്ടതുണ്ട്. 0-അധിഷ്ഠിത ഇൻഡക്സിംഗ് (0-based indexing) ഉപയോഗിക്കുമ്പോൾ ⌊n / 2⌋-ാമത്തെ നോഡാണ് മധ്യഭാഗത്തെ നോഡ്.

ഇത് കാര്യക്ഷമമായി എങ്ങനെ പരിഹരിക്കാം എന്ന് താഴെ നൽകുന്നു.

The Strategy

ഒരു പാസ്സിലൂടെ (one pass) മധ്യഭാഗം കണ്ടെത്താൻ രണ്ട് പോയിന്ററുകൾ ഉപയോഗിക്കുക.

• ഓരോ തവണയും ഒരു സ്റ്റെപ്പ് മാത്രം നീങ്ങുന്ന ഒരു slow pointer ഉപയോഗിക്കുക.
• ഓരോ തവണയും രണ്ട് സ്റ്റെപ്പുകൾ നീങ്ങുന്ന ഒരു fast pointer ഉപയോഗിക്കുക.
• fast pointer അവസാനത്തെ നോഡിൽ എത്തുമ്പോൾ, slow pointer മധ്യഭാഗത്ത് എത്തും.
• slow pointer-ന് തൊട്ടുമുമ്പുള്ള നോഡ് ട്രാക്ക് ചെയ്യാൻ മൂന്നാമതൊരു പോയിന്റർ ഉപയോഗിക്കുക.

The Logic

1. എഡ്ജ് കേസ് (edge case) കൈകാര്യം ചെയ്യുക. ലിസ്റ്റിൽ ഒരു നോഡ് മാത്രമേയുള്ളൂ എങ്കിൽ, null തിരികെ നൽകുക.
2. slow, fast പോയിന്ററുകൾ head-ൽ ആരംഭിക്കുക.
3. fast pointer രണ്ട് സ്റ്റെപ്പും slow pointer ഒരു സ്റ്റെപ്പും നീക്കുക.
4. slow pointer-ന് ഒരു സ്റ്റെപ്പ് പിന്നിലായിരിക്കാൻ ഒരു 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