2095. Delete the Middle Node of a Linked List

Delete the Middle Node of a Linked List

Problem Description 

You are given  head a linked list. Delete the middle node, and return  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

Approach) Two Pointer

Most of the problems related to the linked list can be solved using tracker/pointers i.e slow and fast pointers. In this also we gonna use two pointers first is the slow pointer which will be running one step at a time and the other is the fast pointer which will be running two-step at a time. 

We start traversing through the linked list and what we find at last…. is our fast pointer reached the end of the linked list and the slow pointer is in the middle of the LinkedList…. Now here we have to keep track of the prev of slow pointer also, which will be required to delete the middle node.

Code:

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteMiddle = function(head) {
     if( !head || !head.next ) return null;
     if(!head.next) return null;
     let slow = head, fast = head;
     while(fast != null){
         if(fast.next && fast.next.next && fast.next.next.next){
             slow = slow.next;
             fast = fast.next.next;
         }
         else fast = null;
     }
     slow.next = slow.next.next;
     return head
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem #2095. Delete the Middle Node of a Linked List

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!