Dare2Solve
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
.
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.
null
or None
because there's no middle node to delete.slow
and fast
, both starting at the head of the list. The fast
pointer should move twice as fast as the slow
pointer.slow
pointer one step at a time and the fast
pointer two steps at a time. Stop when the fast
pointer cannot proceed further.fast
pointer reaches the end of the list, the slow
pointer will be at the middle node. Adjust the next
pointer of the node before the slow pointer to skip the middle node, effectively removing it from the list.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.
The algorithm uses O(1) extra space, as only a few pointers are used, and no additional data structures are needed.
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;
}
};
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
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;
}
}
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
};