ಲಿಂಕ್ಡ್ ಲಿಸ್ಟ್ನ ಮಧ್ಯದ ನೋಡ್ ಅನ್ನು ಡಿಲೀಟ್ ಮಾಡಿ
ನೀವು ಸಿಂಗಲಿ ಲಿಂಕ್ಡ್ ಲಿಸ್ಟ್ನಿಂದ (singly linked list) ಮಧ್ಯದ ನೋಡ್ ಅನ್ನು ತೆಗೆದುಹಾಕಬೇಕಾಗಿದೆ. 0-ಆಧಾರಿತ ಇಂಡೆಕ್ಸಿಂಗ್ ಅನ್ನು ಬಳಸಿದರೆ, ಮಧ್ಯದ ನೋಡ್ ಎಂದರೆ ⌊n / 2⌋-ನೇ ನೋಡ್ ಆಗಿದೆ.
ಇದನ್ನು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಹೇಗೆ ಪರಿಹರಿಸಬಹುದು ಎಂಬುದು ಇಲ್ಲಿದೆ.
The Strategy
ಮಧ್ಯದ ಭಾಗವನ್ನು ಒಂದೇ ಪಾಸ್ನಲ್ಲಿ ಕಂಡುಹಿಡಿಯಲು ಎರಡು ಪಾಯಿಂಟರ್ಗಳನ್ನು ಬಳಸಿ.
- ಒಂದೇ ಬಾರಿಗೆ ಒಂದು ಹೆಜ್ಜೆ ಚಲಿಸುವ 'slow pointer' ಅನ್ನು ಬಳಸಿ.
- ಒಂದೇ ಬಾರಿಗೆ ಎರಡು ಹೆಜ್ಜೆ ಚಲಿಸುವ 'fast pointer' ಅನ್ನು ಬಳಸಿ.
- ಫಾಸ್ಟ್ ಪಾಯಿಂಟರ್ ಕೊನೆಯನ್ನು ತಲುಪಿದಾಗ, ಸ್ಲೋ ಪಾಯಿಂಟರ್ ಮಧ್ಯದಲ್ಲಿರುತ್ತದೆ.
- ಸ್ಲೋ ಪಾಯಿಂಟರ್ಗಿಂತ ಹಿಂದಿನ ನೋಡ್ ಅನ್ನು ಟ್ರ್ಯಾಕ್ ಮಾಡಲು ಮೂರನೇ ಪಾಯಿಂಟರ್ ಅನ್ನು ಬಳಸಿ.
The Logic
- ಎಡ್ಜ್ ಕೇಸ್ (edge case) ಅನ್ನು ನಿರ್ವಹಿಸಿ. ಲಿಸ್ಟ್ನಲ್ಲಿ ಕೇವಲ ಒಂದು ನೋಡ್ ಇದ್ದರೆ, null ಅನ್ನು ರಿಟರ್ನ್ ಮಾಡಿ.
- ಸ್ಲೋ ಮತ್ತು ಫಾಸ್ಟ್ ಪಾಯಿಂಟರ್ಗಳನ್ನು head ನಲ್ಲಿ ಇನಿಶಿಯಲೈಸ್ ಮಾಡಿ.
- ಫಾಸ್ಟ್ ಪಾಯಿಂಟರ್ ಅನ್ನು ಎರಡು ಹೆಜ್ಜೆ ಮತ್ತು ಸ್ಲೋ ಪಾಯಿಂಟರ್ ಅನ್ನು ಒಂದು ಹೆಜ್ಜೆ ಚಲಿಸಿ.
- ಸ್ಲೋ ಪಾಯಿಂಟರ್ಗಿಂತ ಒಂದು ಹೆಜ್ಜೆ ಹಿಂದೆ ಇರಲು 'prev' ಪಾಯಿಂಟರ್ ಅನ್ನು ಅಪ್ಡೇಟ್ ಮಾಡಿ.
- ಲೂಪ್ ಮುಗಿದ ನಂತರ, '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