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 <iostream>
2
3struct ListNode {
4 int val;
5 ListNode *next;
6 ListNode() : val(0), next(nullptr) {}
7 ListNode(int x) : val(x), next(nullptr) {}
8 ListNode(int x, ListNode *next) : val(x), next(next) {}
9};
10
11ListNode* deleteMiddle(ListNode* head) {
12 if (!head || !head->next) return nullptr;
13 ListNode* temp = head;
14 int count = 0;
15 while (temp) {
16 count++;
17 temp = temp->next;
18 }
19 int mid = count / 2;
20 ListNode* prev = nullptr;
21 temp = head;
22 while (mid-- > 0) {
23 prev = temp;
24 temp = temp->next;
25 }
26 if (prev) {
27 prev->next = prev->next->next;
28 }
29 return head;
30}
31This C++ implementation uses a similar logic to the C solution. It makes two traversals of the list: one to count the nodes and another to remove the middle node by updating links.
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
This C implementation uses two pointers and a previous pointer to find the middle node and update the links, all in a single pass through the list.