Sponsored
Sponsored
This approach involves traversing the list twice. In the first pass, you count the number of nodes to determine the middle node's index. In the second pass, you reach the middle node and update the links to skip it.
Time Complexity: O(n), where n is the number of nodes.
Space Complexity: O(1).
1#include <stdio.h>
2#include <stdlib.h>
3
4struct ListNode {
5 int val;
6 struct ListNode *next;
7};
8
9struct ListNode* deleteMiddle(struct ListNode* head) {
10 if (!head || !head->next) return NULL;
11 struct ListNode *temp = head;
12 int count = 0;
13 while (temp) {
14 count++;
15 temp = temp->next;
16 }
17 int mid = count / 2;
18 struct ListNode *prev = NULL;
19 temp = head;
20 while (mid-- > 0) {
21 prev = temp;
22 temp = temp->next;
23 }
24 if (prev && prev->next) {
25 prev->next = prev->next->next;
26 }
27 return head;
28}
29This C solution calculates the length of the list first and stores it in the count variable. Then it computes the middle index using count / 2. In the second pass, it traverses to the middle node and bypasses it by updating the next pointer of the previous node.
This approach uses two pointers: a slow pointer and a fast pointer. The fast pointer moves twice as fast as the slow pointer. When the fast pointer reaches the end, the slow pointer will be at the middle node. We can then remove the middle node in a single pass.
Time Complexity: O(n)
Space Complexity: O(1)
1
In the Python solution, slow and fast pointers are used to find the middle node efficiently. The middle node is removed by adjusting pointers in a single list traversal.