LeetCode 2095. Delete the Middle Node of a Linked List

Delete the Middle Node of a Linked List

 

Problem

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, 105].
    1 <= Node.val <= 105

 

---

 

Solution

The key requirements of this problem are as follows:

1. Delete the middle node using 0-based indexing.
2. Return the modified linked list after removing the middle node.

To satisfy these requirements, I used a two-pointer approach.

 

First, initialize three pointers : left, right and prev, all pointing to head.

Using the two-pointer, when tthe left moves to the next node, the right moves two steps at a time.

Therefore, when right reaches the end of the linked list, the left is located at the middle node.

 

During the iteration, prev always keeps tracking just before left.

 

After the end of the loop, left points the middle node and prev.next points to left.

 

By setting prev.next = left.next, the middle node is skipped and removed from the linked list.

 

Since a linked list is connected through next references, once the link is changed, the removed node is no longer reachable and will be deleted by garbage collector.

 

If the list contains only one node or is empty, return None directly.

 

class Solution(object):
    def deleteMiddle(self, head):
        left = head
        right = head
        prev = head

        if not head or not head.next:  
            return None

        while right and right.next:
            prev = left
            left = left.next
            right = right.next.next

        prev.next = left.next

        return head

 

---

https://github.com/K-MarkLee/LeetCode-Practice