LeetCode Challenge #2095. Delete the Middle Node of a Linked List

Question 29 of 75 - LeetCode Weekly Challenge

Day 74 of 100 Days LeetCode Challenge

LeetCode Challenge #2095. Delete the Middle Node of a Linked List

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⁵

C++ Video Solution

Java Video Solution

C++ Solution

				
					
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteMiddle(ListNode* head) {

        if(!head || !head->next) return NULL;

        ListNode* slow=head;
        ListNode* fast=head->next;

        while(fast->next and fast->next->next)
        {
            slow=slow->next;
            if(fast->next)fast=fast->next->next;
        }
        if(slow->next)slow->next=slow->next->next;
        return head;
    }
};

Java Solution

				
					class Solution {
    public ListNode deleteMiddle(ListNode head) {
        if(head.next == null){
            return null;
        }

        ListNode fast = head ;
        ListNode slow = head ;
        ListNode pre = slow ;

        while(fast!=null && fast.next!=null){
            pre = slow ;
            slow = slow.next;
            fast = fast.next.next;
        }

        pre.next = pre.next.next;
        return head ; 
    }
}

Code Explanation

The purpose of this function is to delete the middle node of the linked list.

Let’s see the step-by-step approach:

First of all, we will check the base condition, that if the linked list is empty or contains only one node. It means there is no element to delete so, it returns ‘NULL’.
For finding the middle element of the linked list, a two-pointer approach is used. Two pointers, ‘slow’ and ‘fast’ are initialised at the head of the linked list. In which, the ‘fast’ pointer moves twice as fast as the ‘slow’ pointer.
We have to keep in mind that we have to stop the linked list before it reaches to the last node and for that purpose we used a while loop in which

(fast->next && fast->next->next-> ) and
(slow= slow->next)

Once the middle node is identified using the two-pointer approach, the ‘next’ pointer is adjusted to skip the middle node, effectively removing the middle element from the linked list.
The head of the modified linked list is returned.

Question 29 of 75 - LeetCode Weekly Challenge

Day 74 of 100 Days LeetCode Challenge

LeetCode Challenge #2095. Delete the Middle Node of a Linked List

C++ Video Solution

Java Video Solution

C++ Solution

Java Solution

Code Explanation

Happy Coding with edSlash

Talk to our Industry Experts for Career Counselling

Company

Platform

Resources

Get in touch