లింక్డ్ లిస్ట్ యొక్క మధ్య నోడ్ను తొలగించండి
మీరు ఒక సింగ్లీ లింక్డ్ లిస్ట్ నుండి మధ్య నోడ్ను తొలగించాల్సి ఉంటుంది. 0-బేస్డ్ ఇండెక్సింగ్ను ఉపయోగించినప్పుడు, మధ్య నోడ్ అనేది ⌊n / 2⌋-వ నోడ్.
దీనిని సమర్థవంతంగా ఎలా పరిష్కరించాలో ఇక్కడ చూడండి.
వ్యూహం
ఒకే పాస్లో మధ్య నోడ్ను కనుగొనడానికి రెండు పాయింటర్లను ఉపయోగించండి.
- ఒక్కోసారి ఒక అడుగు మాత్రమే ముందుకు కదిలే స్లో పాయింటర్ను ఉపయోగించండి.
- ఒక్కోసారి రెండు అడుగులు ముందుకు కదిలే ఫాస్ట్ పాయింటర్ను ఉపయోగించండి.
- ఫాస్ట్ పాయింటర్ చివరికి చేరుకున్నప్పుడు, స్లో పాయింటర్ మధ్యలో ఉంటుంది.
- స్లో పాయింటర్ కంటే ముందున్న నోడ్ను ట్రాక్ చేయడానికి మూడవ పాయింటర్ను ఉంచండి.
తర్కం
- ఎడ్జ్ కేస్ను (edge case) హ్యాండిల్ చేయండి. లిస్ట్లో ఒకే నోడ్ ఉంటే, null రిటర్న్ చేయండి.
- స్లో మరియు ఫాస్ట్ పాయింటర్లను హెడ్ (head) వద్ద ప్రారంభించండి.
- ఫాస్ట్ పాయింటర్ను రెండు అడుగులు మరియు స్లో పాయింటర్ను ఒక అడుగు ముందుకు జరపండి.
- స్లో పాయింటర్ కంటే ఒక అడుగు వెనుక ఉండేలా 'prev' పాయింటర్ను అప్డేట్ చేయండి.
- లూప్ ముగిసిన తర్వాత, 'prev' నోడ్ను 'slow' తర్వాత ఉన్న నోడ్కు లింక్ చేయండి. దీనివల్ల మధ్య నోడ్ స్కిప్ అవుతుంది.
సంక్లిష్టత
- Time Complexity: O(n). మీరు లిస్ట్ను ఒకసారి మాత్రమే ట్రావర్స్ చేస్తారు.
- Space Complexity: O(1). మీరు కేవలం మూడు పాయింటర్లను మాత్రమే ఉపయోగిస్తారు.
PHP ఇంప్లిమెంటేషన్
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