लिंकड लिस्टचा मधला नोड (Middle Node) हटवा
तुम्हाला सिंगलली लिंकड लिस्टमधून (singly linked list) मधला नोड काढून टाकणे आवश्यक आहे. 0-आधारित इंडेक्सिंग (0-based indexing) वापरल्यास, मधला नोड हा ⌊n / 2⌋-वा नोड असतो.
हे कार्यक्षमतेने कसे सोडवायचे ते खाली दिले आहे.
रणनीती (The Strategy)
एकाच पासमध्ये (one pass) मधला नोड शोधण्यासाठी दोन पॉइंटर्सचा वापर करा.
- एक स्लो पॉइंटर (slow pointer) वापरा जो एका वेळी एक पाऊल पुढे सरकतो.
- एक फास्ट पॉइंटर (fast pointer) वापरा जो एका वेळी दोन पावले पुढे सरकतो.
- जेव्हा फास्ट पॉइंटर शेवटपर्यंत पोहोचतो, तेव्हा स्लो पॉइंटर मधल्या नोडवर असतो.
- स्लो पॉइंटरच्या आधीचा नोड ट्रॅक करण्यासाठी तिसरा पॉइंटर ठेवा.
लॉजिक (The Logic)
- एज केस (edge case) हाताळा. जर लिस्टमध्ये फक्त एकच नोड असेल, तर null रिटर्न करा.
- स्लो आणि फास्ट पॉइंटर्स 'head' वर इनिशियलाइज करा.
- फास्ट पॉइंटर दोन पावले आणि स्लो पॉइंटर एक पाऊल पुढे सरकवा.
- स्लो पॉइंटरच्या एक पाऊल मागे राहण्यासाठी 'prev' पॉइंटर अपडेट करा.
- लूप संपल्यानंतर, 'prev' नोडला 'slow' नंतरच्या नोडशी जोडा. यामुळे मधला नोड वगळला (skip) जातो.
कॉम्प्लेक्सिटी (Complexity)
- टाइम कॉम्प्लेक्सिटी (Time Complexity): O(n). तुम्ही लिस्ट एकदा ट्रॅव्हर्स (traverse) करता.
- स्पेस कॉम्प्लेक्सिटी (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;
}
Source: https://dev.to/mdarifulhaque/2095-delete-the-middle-node-of-a-linked-list-4jf1