Problem
Given the head of a singly linked list, delete the middle node and return the head of the modified list.The middle node is the node at index
n / 2, using zero-based indexing, where n is the number of nodes in the linked list. If there are two middle positions, the second middle node is considered the middle node.
Example(s)
Consider the following examples to understand the expected input and output.Example 1
Input
head = [1,3,4,7,1,2,6]Output
[1,3,4,1,2,6]Example 2
Input
head = [1,2,3,4]Output
[1,2,4]Solution
This solution uses the Fast and Slow Pointer technique. Theslow pointer moves one node at a time, while the fast pointer moves two nodes at a time.
When the
fast pointer reaches the end of the list, the slow pointer is positioned around the middle. We use a prev pointer to keep track of the node before slow. Once the middle node is found, we remove it by changing prev.next to slow.next.
class Solution {
public ListNode deleteMiddle(ListNode head) {
if (head.next == null) {
return null;
}
ListNode slow = head;
ListNode fast = head;
ListNode prev = null;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = slow.next;
return head;
}
}Complexity
The fast and slow pointers traverse the linked list in a single pass, so the time complexity isO(n), where n is the number of nodes.
The solution uses only a few pointers, so the extra space complexity is
O(1).