Delete the Middle Node of a Linked List

Medium

Apple

1 view

Topics:

Linked Lists

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.

For 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:

The number of nodes in the list is in the range [1, 10⁵].
1 <= Node.val <= 10⁵

Delete the Middle Node of a Linked List

Medium

Apple

1 view

Topics:

Linked Lists

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.

For 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:

The number of nodes in the list is in the range [1, 10⁵].
1 <= Node.val <= 10⁵

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the linked list ever be empty or contain only one node?
What data type are the values stored in the linked list nodes?
If the list has an even number of nodes, and thus two middle nodes, by 'second middle node', do you mean the *later* of the two when traversing from head to tail?
Should I modify the original linked list in place, or return a new linked list with the middle node removed?
Are there any memory constraints I should be aware of?

Brute Force Solution

Approach

The goal is to remove the middle item from a linked list. The brute force method involves figuring out how many items are in the list and then walking to the middle to remove it.

Here's how the algorithm would work step-by-step:

First, count how many items are in the entire list. This tells you the total size.
Figure out which item is in the exact middle based on the total size. If there are an even number of items, it's one of the two in the middle. We'll focus on the first one of the middle two.
Starting from the beginning of the list, move through the list, item by item, until you arrive at the item just before the middle item you want to remove.
Once you are at the item before the middle one, carefully bypass the middle item by connecting the item before it directly to the item after the middle one. This effectively removes the middle item from the list.
The list is now updated with the middle item gone.

Code Implementation

def delete_middle_node(head):
    if not head or not head.next:
        return None

    list_size = 0
    current_node = head
    while current_node:
        list_size += 1
        current_node = current_node.next

    # Determine the middle node index
    middle_node_index = list_size // 2

    # Traverse to the node before the middle node
    current_node = head
    for _ in range(middle_node_index - 1):
        current_node = current_node.next

    # Bypass the middle node to delete it
    current_node.next = current_node.next.next

    return head

Big(O) Analysis

Time Complexity

O(n) – The algorithm first iterates through the linked list once to determine its size, which takes O(n) time, where n is the number of nodes in the list. Then, it iterates again, up to the middle of the list, to find the node preceding the middle node, which takes O(n/2) time. Since O(n/2) simplifies to O(n), the overall time complexity is dominated by the linear traversals and is therefore O(n).

Space Complexity

O(1) – The provided algorithm calculates the middle node's position by first counting the total number of nodes. This count is stored in a single variable. After determining the middle, it iterates to the node before the middle for deletion using another single variable to track current position. The algorithm uses a fixed number of variables regardless of the size (N) of the linked list; therefore, it doesn't require extra space that scales with the input size. The space complexity is constant.

Optimal Solution

Approach

The goal is to remove the middle item from a connected chain of items. Since we don't know the exact length beforehand, we use a clever trick to find the middle quickly without counting everything first.

Here's how the algorithm would work step-by-step:

Use two markers to move through the chain. One marker moves one item at a time, while the other moves twice as fast.
When the faster marker reaches the end of the chain, the slower marker will be pointing at the middle item.
Once the middle item is located, change the 'next' pointer of the item before it to point to the item after the middle one. This effectively removes the middle item from the chain.

Code Implementation

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def delete_middle_node(head_node):
    if head_node is None or head_node.next is None:
        return None

    slow_pointer = head_node
    fast_pointer = head_node
    previous_to_slow = None

    # Traverse list using two pointers to find middle node
    while fast_pointer is not None and fast_pointer.next is not None:
        fast_pointer = fast_pointer.next.next
        previous_to_slow = slow_pointer

        slow_pointer = slow_pointer.next

    # At this point, slow_pointer points to the middle node.
    # We need to update the previous node's next pointer.
    if previous_to_slow is not None:

        # This removes the middle node by skipping over it.
        previous_to_slow.next = slow_pointer.next

    return head_node

Big(O) Analysis

Time Complexity

O(n) – The algorithm uses two pointers, a slow pointer and a fast pointer, to traverse the linked list. The fast pointer moves twice as fast as the slow pointer. The while loop iterates until the fast pointer reaches the end of the list. Since the fast pointer traverses the list at twice the speed of the slow pointer, the slow pointer reaches the middle node when the fast pointer reaches the end. Therefore, the algorithm effectively traverses the linked list once. Hence, the time complexity is O(n), where n is the number of nodes in the linked list.

Space Complexity

O(1) – The provided algorithm uses two pointers (markers), one moving at a single step and another at double the step, to locate the middle node. These pointers are simple variables that store node references and do not depend on the size of the linked list (N). No additional data structures, such as arrays or hash maps, are created to store intermediate results or track visited nodes. Therefore, the auxiliary space used is constant, resulting in a space complexity of O(1).

Edge Cases

Case	How to Handle
Empty list (head is null)	Return null immediately as there's nothing to delete.
List with one node	Delete the only node by setting the head to null and returning null.
List with two nodes	Delete the second middle node, which is the second node in the list.
List with an even number of nodes (e.g., 4 nodes)	Delete the second middle node (the node at position n/2 where n is number of nodes, considering 0-based indexing).
List with an odd number of nodes (e.g., 5 nodes)	Delete the middle node (the node at position (n-1)/2 where n is number of nodes, considering 0-based indexing).
Very long list (potential for slow pointer to catch up very late)	The fast and slow pointer approach remains efficient regardless of list length, as it only requires one traversal.
List with duplicate values; middle node has same value as other nodes	The slow and fast pointer method finds the middle node's position independent of value, ensuring correct deletion.
Memory constraints preventing list copying to find length	The slow and fast pointer approach operates in place without needing to copy the list, making it memory-efficient.