
Problem Statement
In this problem, you are provided with the head of a singly linked list and your task is to remove the middle node from this list and return the head of the updated list. The middle node is defined on the basis of 0-based indexing; it is the node located at position ⌊n / 2⌋, where n is the total number of nodes in the list and ⌊x⌋ denotes the greatest integer less than or equal to x. The concept behind choosing ⌊n / 2⌋ is essentially picking the central node in an odd-numbered list and the first of the two middle nodes in an even-numbered list.
Examples
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
- The number of nodes in the list is in the range
[1, 105]
. 1 <= Node.val <= 105
Approach and Intuition
The problem can be effectively approached by following these defined steps:
- Compute the size of the linked list. This involves traversing the list from the head to the end and counting the nodes.
- Determine the middle node's index using the formula ⌊n / 2⌋.
- If the list has only one node, simply return
None
because deleting the only node leaves the list empty. - Traverse the list again up to the node just before the middle node. This is necessary because in singly linked lists, you can only remove a node if you have access to its predecessor.
- Adjust the next pointer of the node before the middle node (if it exists) to bypass the middle node, thereby removing it from the list.
- Return the head of the modified linked list.
From the given examples:
- In example 1, list
[1,3,4,7,1,2,6]
has 7 nodes, thus the middle node is the one at index ⌊7/2⌋ = 3 (value 7). After removing node 7, the result is[1,3,4,1,2,6]
. - Example 2’s input list
[1,2,3,4]
has n = 4, so the middle is at index ⌊4/2⌋ = 2 (value 3). Post-removal, the list updates to[1,2,4]
. - With an input list of
[2,1]
in example 3, n = 2 puts the middle node at index 1 (value 1), and removing it leaves us with[2]
.
This method leverages straightforward list traversal techniques and provides an intuitive way to access and remove the middle node in a single pass through the list, followed by another partial pass to the determined middle index.
Solutions
- C++
- Java
- JavaScript
class Solution {
public:
ListNode* removeMiddleNode(ListNode* start) {
if (start -> next == nullptr)
return nullptr;
ListNode *slowPointer = start, *fastPointer = start -> next -> next;
while (fastPointer != nullptr && fastPointer -> next != nullptr) {
slowPointer = slowPointer -> next;
fastPointer = fastPointer -> next -> next;
}
slowPointer -> next = slowPointer -> next -> next;
return start;
}
};
This summary guides you through a C++ implementation designed to delete the middle node from a singly linked list. The goal is to return the modified linked list with one less node, specifically without the middle node.
- The solution employs the two-pointer technique using a
slowPointer
and afastPointer
. - Begin by checking if the linked list is extremely short. If the start node's next points to
nullptr
, there's only one element, or the list is empty, in which case returnnullptr
. - Initialize
slowPointer
at the start node andfastPointer
several steps ahead — specifically, at the second node'snext
if it exists. This sets up for the traversal wherefastPointer
will move twice as fast asslowPointer
. - Traverse through the linked list:
- Move
slowPointer
one step at a time. - Move
fastPointer
two steps at a time.
- Move
- Continue this until
fastPointer
is either at the end of the list or has no further nodes (nullptr
) to jump to. - Adjust the
next
pointer of theslowPointer
to skip its next node (effectively removing the middle node sinceslowPointer
would be just before the middle whenfastPointer
reaches the end). - Return the modified
start
of the linked list as the final result.
This method efficiently locates and removes the middle node in O(n) time with O(1) space complexity, utilizing a classic fast and slow pointer strategy.
class Solution {
public ListNode removeMiddleNode(ListNode start) {
if (start.next == null)
return null;
ListNode slow = start, fast = start.next.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
slow.next = slow.next.next;
return start;
}
}
The solution provided addresses the problem of deleting the middle node from a linked list using Java. The approach implemented in the solution utilizes the two-pointer technique, consisting of "slow" and "fast" pointers, to determine the middle of the list efficiently.
Here's a breakdown of how the solution operates:
Check if the
start.next
is null, indicating the list only contains one node. If true, return null as the list will be empty after removing the middle.Initialize two pointers,
slow
starting at the head of the list andfast
starting at the second node's next node (two steps ahead).Iterate through the list while
fast
andfast.next
are not null. Moveslow
one step for each two stepsfast
takes. Whenfast
reaches the end of the list,slow
will be exactly before the middle node of the linked list.Remove the middle element by setting
slow.next
toslow.next.next
, effectively skipping over the middle node.Return the modified linked list starting from
start
.
This method ensures that the middle node is successfully removed while maintaining the integrity of the linked list, and it works efficiently with a time complexity of O(n), where n is the number of nodes in the list.
var removeMiddleNode = function(headNode) {
if (headNode.next == null)
return null;
let slowPointer = headNode, fastPointer = headNode.next.next;
while (fastPointer != null && fastPointer.next != null) {
slowPointer = slowPointer.next;
fastPointer = fastPointer.next.next;
}
slowPointer.next = slowPointer.next.next;
return headNode;
};
The provided JavaScript function, removeMiddleNode
, targets deleting the middle node from a singly linked list. Here's a breakdown of how the function operates:
- Initially, it checks if the
headNode
has no following nodes by checkingheadNode.next
. If this node is null, the function returns null, indicating the list was already empty or had only one element. - Two pointers,
slowPointer
andfastPointer
, are used for traversal of the linked list.slowPointer
progresses one node at a time, whilefastPointer
moves two nodes at a time. This difference allowsslowPointer
to reach the middle of the list whenfastPointer
reaches its end. - A loop continues until
fastPointer
either becomes null or has no next node, ensuring traversal to the end of the list. During each iteration,slowPointer
andfastPointer
are advanced accordingly. - Once the loop concludes,
slowPointer
directly links to the node after its next node (slowPointer.next = slowPointer.next.next
), effectively skipping the middle node and removing it from the list. - Finally, the modified list with the middle node removed is returned by handing back the
headNode
.
This solution accomplishes the middle node removal efficiently by using the two-pointer technique to avoid counting or recalculating the list's length.
No comments yet.