લિંક્ડ લિસ્ટનો મધ્યમ નોડ (Middle Node) ડિલીટ કરો
તમારે સિંગલી લિંક્ડ લિસ્ટમાંથી મધ્યમ નોડ દૂર કરવાની જરૂર છે. 0-આધારિત ઇન્ડેક્સિંગનો ઉપયોગ કરતા, મધ્યમ નોડ એ ⌊n / 2⌋-મો નોડ છે.
તેને કાર્યક્ષમ રીતે કેવી રીતે ઉકેલવું તે અહીં છે.
વ્યૂહરચના (The Strategy)
એક જ પાસમાં મધ્યમ નોડ શોધવા માટે બે પોઇન્ટર્સનો ઉપયોગ કરો.
- એક સ્લો પોઇન્ટર (slow pointer) નો ઉપયોગ કરો જે એક સમયે એક સ્ટેપ આગળ વધે છે.
- એક ફાસ્ટ પોઇન્ટર (fast pointer) નો ઉપયોગ કરો જે એક સમયે બે સ્ટેપ આગળ વધે છે.
- જ્યારે ફાસ્ટ પોઇન્ટર અંત સુધી પહોંચે છે, ત્યારે સ્લો પોઇન્ટર મધ્યમાં હશે.
- સ્લો પોઇન્ટર પહેલાના નોડને ટ્રેક કરવા માટે ત્રીજા પોઇન્ટરનો ઉપયોગ કરો.
લોજિક (The Logic)
- એજ કેસ (edge case) હેન્ડલ કરો. જો લિસ્ટમાં માત્ર એક જ નોડ હોય, તો null રિટર્ન કરો.
- સ્લો અને ફાસ્ટ પોઇન્ટર્સને હેડ (head) પર ઇનિશિયલાઇઝ કરો.
- ફાસ્ટ પોઇન્ટરને બે સ્ટેપ અને સ્લો પોઇન્ટરને એક સ્ટેપ આગળ વધારો.
- સ્લો પોઇન્ટરથી એક સ્ટેપ પાછળ રહેવા માટે 'prev' પોઇન્ટરને અપડેટ કરો.
- લૂપ પૂરી થયા પછી, 'prev' નોડને 'slow' પછીના નોડ સાથે જોડો. આનાથી મધ્યમ નોડ સ્કીપ થઈ જશે.
કોમ્પ્લેક્સિટી (Complexity)
- ટાઈમ કોમ્પ્લેક્સિટી: O(n). તમે લિસ્ટને એકવાર ટ્રેવર્સ કરો છો.
- સ્પેસ કોમ્પ્લેક્સિટી: 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