हिन्दी flagहिन्दी  
CLOSE

Suggested:

🛠️ Settings

Problem Statement

Given a singly linked list, we are tasked with deleting the middle node. If the list contains an even number of nodes, there are two middle nodes. In such cases, we'll delete the second middle node.

Examples

Example 1:

Input: List = [1, 2, 3, 4, 5]
Output: [1, 2, 4, 5]
Explanation: As the length of the linked list is odd. Thus it has a single middle element.
Example 2:

Input: List = [1, 2, 3, 4]
Output: [1, 2, 4]
Explanation: As the length of the linked list is even. Thus it has two middle element [2, 3] and we need to delete the later one. So 3 is deleted.
Example 3:

Input: List = [1, 2, 3, 4, 5, 6]
Output: [1, 2, 3, 5, 6]
Explanation: As the length of the linked list is even. Thus it has two middle element [3, 4] and we need to delete the later one. So 4 is deleted.

Different Approaches

1️⃣ Naive Approach Counting Node

Intuition:

The brute force approach is to first find the length of the list by traversing the entire list. After getting the length of the list we find the link before middle element location by (int)n/2.

For even length, middle element location  = 4/2 => 2

For odd length, middle element location = 5/2 => 2

Thus with by n/2, returns the one link before the middle element and we iterate till this node. After that delete the next element and set the next of n/2 node.

Code:

#include <bits/stdc++.h>

using namespace std;

// Definition of singly linked list:
struct ListNode
{
    int val;
    ListNode *next;
    ListNode()
    {
        val = 0;
        next = NULL;
    }
    ListNode(int data1)
    {
        val = data1;
        next = NULL;
    }
    ListNode(int data1, ListNode *next1)
    {
        val = data1;
        next = next1;
    }
};

class Solution {
public:
    // Function to delete middle node of linked list
    ListNode* deleteMiddle(ListNode* head) {
        /* Edge case: if the list is empty 
         * or has only one node, return null */
        if (head == nullptr || head->next == nullptr) {
            delete head;
            return nullptr;
        }

        // Temporary node to traverse
        ListNode* temp = head;
        
        // Variable to store number of nodes
        int n = 0;
        
        /* Loop to count the number of nodes 
        in the linked list */
        while (temp != nullptr) {
            n++;
            temp = temp->next;
        }
        
        // Index of the middle node
        int middleIndex = n / 2;
        
        // Reset temporary node 
        // to beginning of linked list
        temp = head;
        
        /* Loop to find the node 
        just before the middle node */
        for (int i = 1; i < middleIndex; i++) {
            temp = temp->next;
        }
        
        // If the middle node is found
        if (temp->next != nullptr) {
            // Create pointer to the middle node
            ListNode* middle = temp->next;
            
            // Adjust pointers to skip middle node
            temp->next = temp->next->next;
            
            /* Free the memory allocated 
             * to the middle node */
            delete middle;
        }
        
        // Return head
        return head;
    }
};

// Function to print the linked list
void printLL(ListNode* head) {
    ListNode* temp = head;
    while (temp != nullptr) {
        cout << temp->val << " ";
        temp = temp->next;
    }
    cout << endl;
}

int main() {
    // Creating a sample linked list: 
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    
    // Display the original linked list
    cout << "Original Linked List: ";
    printLL(head);

    // Deleting the middle node
    Solution solution;
    head = solution.deleteMiddle(head);

    // Displaying the updated linked list
    cout << "Updated Linked List: ";
    printLL(head);

    return 0;
}

2️⃣ Two Pointer Approach

Intuition:

We observed that in order to delete the middle node, we need to stop the traversing at the link before the middle node. So that we can set its next pointer to the next pointer of middle element.

We can achieve it by using an extra node pointer “previous” pointing to the previous node as we advances the slow pointer.

OR

We can advances the fast pointer by two steps before starting the traversal, such that when fast pointer pointing to the last element. The slow pointer will be pointing to the node before the middle element.

Dry Run:

1 -> 2 -> 3 -> 4 -> 5

We want to delete the middle node, which is 3.

Initially:
1 (slow, fast) -> 2 -> 3 -> 4 -> 5
prev = nullptr
First Iteration:
1 (prev) -> 2 (slow) -> 3 (fast) -> 4 -> 5
Second Iteration:
1 -> 2 (prev) -> 3 (slow) -> 4 -> 5 (fast)

fast has reached the end such that it's next is nullptr
slow is pointing to the middle node, which is to be deleted.
Final List:
1 -> 2 -> 4 -> 5

Code:

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

void deleteMiddleNode(Node* head) {
    if (head == nullptr || head->next == nullptr) {
        return; // No middle node if list has 0 or 1 nodes
    }

    Node* slow = head;
    Node* fast = head;
    Node* prev = nullptr;

    while (fast != nullptr && fast->next != nullptr) {
        prev = slow;
        slow = slow->next;
        fast = fast->next->next;
    }

    // Delete the middle node pointed to by slow
    prev->next = slow->next;
    delete slow;
}

void printList(Node* head) {
    while (head != nullptr) {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    head->next->next->next->next = new Node(5);

    cout << "Original List: ";
    printList(head);

    deleteMiddleNode(head);

    cout << "List after deleting middle node: ";
    printList(head);

    return 0;
}

OR

#include <bits/stdc++.h>

using namespace std;

class Node {
   public:
    int data;
    Node* next;

    Node(int value) {
        data = value;
        next = nullptr;
    }
};

Node* deleteMiddleNode(Node* head) {
    Node* slow = head;
    Node* fast = head;

    fast = fast->next->next;

    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }

    Node* deleteNode = slow->next;

    slow->next = deleteNode->next;

    delete deleteNode;

    return head;
}

int main() {
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    // head->next->next->next->next = new Node(5);
    // head->next->next->next->next->next = new Node(6);

    Node* iterator = deleteMiddleNode(head);
    while (iterator != nullptr) {
        cout << iterator->data << endl;
        iterator = iterator->next;
    }
    return 0;
}

Complexity Analysis:

  • Time Complexity: O(N/2) because the code traverses the linked list using the Tortoise and Hare approach. The code increments both 'slow' and 'fast' pointers at different rates, effectively covering about half the list before reaching the midpoint, hence the time complexity of the algorithm is O(N/2) ~ O(N).
  • Space Complexity: O(1) because the code uses a constant amount of extra space regardless of the size of the input (linked list). It doesn't use any additional data structures in proportion to the input size.
Your experience on this site will be improved by allowing cookies Cookie Policy