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 <= 105This 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.
This 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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of nodes.
Space Complexity: O(1).
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Approach 1: Two-Pass Method | Time Complexity: O(n), where n is the number of nodes. |
| Approach 2: Two-Pointer Method | Time Complexity: O(n) |
This Algorithm is SUPER HELPFUL for Coding Interviews! | Fast & Slow Pointers for Linked Lists • Greg Hogg • 225,901 views views
Watch 9 more video solutions →Practice Delete the Middle Node of a Linked List with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor