
Description
The problem requires deleting the middle node of a singly linked list. If the list has an even number of nodes, the function should delete the second of the two middle nodes. The task is to return the head of the modified list after the middle node has been removed. If the list is empty or has only one node, the function should return null
or None
.
Intuition
To find the middle of the list efficiently, the fast and slow pointer approach is used. The slow pointer moves one step at a time while the fast pointer moves two steps at a time. By the time the fast pointer reaches the end of the list, the slow pointer will be pointing to the middle node. Once the middle node is found, it can be removed by adjusting the next
pointer of the previous node.
Approach
- Edge Case Handling: If the list is empty or contains only one node, return
null
orNone
because there's no middle node to delete. - Initialize Pointers: Use two pointers,
slow
andfast
, both starting at the head of the list. Thefast
pointer should move twice as fast as theslow
pointer. - Find the Middle Node: Move the
slow
pointer one step at a time and thefast
pointer two steps at a time. Stop when thefast
pointer cannot proceed further. - Delete the Middle Node: When the
fast
pointer reaches the end of the list, theslow
pointer will be at the middle node. Adjust thenext
pointer of the node before the slow pointer to skip the middle node, effectively removing it from the list. - Return the Modified List: After the middle node is removed, return the head of the list.
Complexity
Time Complexity:
The algorithm runs in O(n) time, where n is the number of nodes in the list. This is because the list is traversed once.
Space Complexity:
The algorithm uses O(1) extra space, as only a few pointers are used, and no additional data structures are needed.
Code
C++
class Solution {
public:
ListNode* deleteMiddle(ListNode* head) {
if (!head || !head->next) {
return nullptr;
}
ListNode *slow = head, *fast = head;
fast = fast->next->next;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
slow->next = slow->next->next;
return head;
}
};
Python
class Solution:
def deleteMiddle(self, head: ListNode) -> ListNode:
if not head or not head.next:
return None
slow, fast = head, head
fast = fast.next.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
slow.next = slow.next.next
return head
Java
class Solution {
public ListNode deleteMiddle(ListNode head) {
if (head == null || head.next == null) {
return null;
}
ListNode slow = head, fast = head;
fast = fast.next.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
slow.next = slow.next.next;
return head;
}
}
JavaScript
var deleteMiddle = function (head) {
if (!head || !head.next) {
return null
}
let slow = head, fast = head
fast = fast.next.next
while (fast !== null && fast.next !== null) {
slow = slow.next
fast = fast.next.next
}
slow.next = slow.next.next
return head
};