You are given the head of a linked list. Delete the middle node, and return the head of the modified linked list.
The middle node of a linked list of size n is the ⌊n / 2⌋th node from the start using 0-based indexing, where ⌊x⌋ denotes the largest integer less than or equal to x.
n = 1, 2, 3, 4, and 5, the middle nodes are 0, 1, 1, 2, and 2, respectively.Example 1:
Input: head = [1,3,4,7,1,2,6] Output: [1,3,4,1,2,6] Explanation: The above figure represents the given linked list. The indices of the nodes are written below. Since n = 7, node 3 with value 7 is the middle node, which is marked in red. We return the new list after removing this node.
Example 2:
Input: head = [1,2,3,4] Output: [1,2,4] Explanation: The above figure represents the given linked list. For n = 4, node 2 with value 3 is the middle node, which is marked in red.
Example 3:
Input: head = [2,1] Output: [2] Explanation: The above figure represents the given linked list. For n = 2, node 1 with value 1 is the middle node, which is marked in red. Node 0 with value 2 is the only node remaining after removing node 1.
Constraints:
[1, 105].1 <= Node.val <= 105In #2095 Delete the Middle Node of a Linked List, the goal is to remove the middle node and return the updated list. The most efficient strategy uses the two-pointer technique. Maintain a slow pointer that moves one step at a time and a fast pointer that moves two steps. When the fast pointer reaches the end, the slow pointer will be positioned at the middle node.
To delete the middle element, keep track of the node just before the slow pointer and update its next reference to skip the middle node. Special handling is needed when the list contains only one node, since deleting the middle results in an empty list.
This approach traverses the list only once, making it efficient for large inputs. It avoids counting nodes or performing multiple passes, which keeps the implementation clean and optimal.
Time Complexity: O(n) for a single traversal. Space Complexity: O(1) since only pointers are used.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Two Pointers (Slow & Fast) | O(n) | O(1) |
Greg Hogg
Use these hints if you're stuck. Try solving on your own first.
If a point with a speed s moves n units in a given time, a point with speed 2 * s will move 2 * n units at the same time. Can you use this to find the middle node of a linked list?
If you are given the middle node, the node before it, and the node after it, how can you modify the linked list?
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
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The fast and slow pointer technique helps locate the middle node in a single traversal. This avoids counting nodes first, which would require two passes and make the algorithm less efficient.
Yes, linked list pointer problems like this are commonly asked in technical interviews at FAANG and other top companies. They test understanding of pointer manipulation, edge cases, and efficient traversal techniques.
The optimal approach uses the fast and slow pointer technique. The fast pointer moves two steps while the slow pointer moves one step, ensuring the slow pointer reaches the middle when the fast pointer reaches the end. Then the node before the middle is updated to skip it.
A singly linked list is the core data structure in this problem. Efficient manipulation of node pointers allows you to remove the middle element without additional memory structures.
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.