Delete the middle node in LL

Intuition

First, count all the nodes by going through the list. Then, start again from the beginning and go to the node just before the middle one. Change the links to skip over the middle node, taking it out of the list.

Approach

First, count all the nodes in the linked list to find out how many there are. Then, figure out which node is in the middle by dividing the total number of nodes by 2.

Next, start from the beginning of the list and move through the nodes until you reach the middle one.

When you reach the middle node, remove it by linking the previous node directly to the node after the middle one. Finally, clear the space that was taken up by the middle node.

Dry Run

Solution

#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;
}
import java.util.*;

// Definition of singly linked list:
class 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 {
    // Function to delete middle node of linked list
    public ListNode deleteMiddle(ListNode head) {
        /* Edge case: if the list is empty 
         * or has only one node, return null */
        if (head == null || head.next == null) {
            return null;
        }

        // 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 != null) {
            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 != null) {
            // 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 */
            middle = null;
        }
        
        // Return head
        return head;
    }

    // Function to print the linked list
    public static void printLL(ListNode head) {
        ListNode temp = head;
        while (temp != null) {
            System.out.print(temp.val + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // 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
        System.out.print("Original Linked List: ");
        printLL(head);

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

        // Displaying the updated linked list
        System.out.print("Updated Linked List: ");
        printLL(head);
    }
}
# Definition of singly linked list:
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    # Function to delete middle node of linked list
    def deleteMiddle(self, head):
        """ Edge case: if the list is empty 
        or has only one node, return null """
        if not head or not head.next:
            return None

        # Temporary node to traverse
        temp = head
        
        # Variable to store number of nodes
        n = 0
        
        """ Loop to count the number of nodes 
        in the linked list """
        while temp:
            n += 1
            temp = temp.next
        
        # Index of the middle node
        middleIndex = n // 2
        
        # Reset temporary node 
        # to beginning of linked list
        temp = head
        
        """ Loop to find the node 
        just before the middle node """
        for _ in range(1, middleIndex):
            temp = temp.next
        
        # If the middle node is found
        if temp.next:
            # Create pointer to the middle node
            middle = temp.next
            
            # Adjust pointers to skip middle node
            temp.next = temp.next.next
            
            """ Free the memory allocated 
            to the middle node """
            del middle
        
        # Return the head of the modified linked list
        return head

# Function to print the linked list
def printLL(head):
    temp = head
    while temp:
        print(temp.val, end=" ")
        temp = temp.next
    print()

# Creating a sample linked list: 
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)

# Display the original linked list
print("Original Linked List: ", end="")
printLL(head)

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

# Displaying the updated linked list
print("Updated Linked List: ", end="")
printLL(head)
// Definition of singly linked list:
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

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

        // Temporary node to traverse
        let temp = head;
        
        // Variable to store number of nodes
        let n = 0;
        
        /* Loop to count the number of nodes 
        in the linked list */
        while (temp !== null) {
            n++;
            temp = temp.next;
        }
        
        // Index of the middle node
        const middleIndex = Math.floor(n / 2);
        
        // Reset temporary node 
        // to beginning of linked list
        temp = head;
        
        /* Loop to find the node 
        just before the middle node */
        for (let i = 1; i < middleIndex; i++) {
            temp = temp.next;
        }
        
        // If the middle node is found
        if (temp.next !== null) {
            // Create pointer to the middle node
            const middle = temp.next;
            
            // Adjust pointers to skip middle node
            temp.next = temp.next.next;
            
        }
        
        // Return the head of the modified linked list
        return head;
    }
}

// Function to print the linked list
function printLL(head) {
    let temp = head;
    while (temp !== null) {
        process.stdout.write(temp.val + " ");
        temp = temp.next;
    }
    console.log();
}

// Creating a sample linked list: 
let 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
process.stdout.write("Original Linked List: ");
printLL(head);

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

// Displaying the updated linked list
process.stdout.write("Updated Linked List: ");
printLL(head);

Time Complexity

Time Complexity: O(N + N/2) because the loop traverses the entire linked list once to count the total number of nodes then the loop iterates halfway through the linked list to reach the middle node. Hence, the time complexity is O(N + N/2) ~ O(N).

Space Complexity: O(1) because the code uses a constant amount of extra space regardless of the size of the linked list. It doesn't use any additional data structures in proportion to the input size.

Intuition

The brute force method involves traversing the linked list twice to find and delete the middle node. To make this more efficient,we use the Tortoise and Hare approach which helps in finding the middle node in one traversal by moving the 'slow' pointer one step and the 'fast' pointer two steps at a time.

This ensures the 'slow' pointer reaches the middle when the 'fast' pointer reaches the end. To have 'slow' reach just before the middle, the 'fast' pointer gets a head start.

Approach

Initialization: Check if the list is empty or has only one node. If so, there is no middle node to delete, so return NULL. Set 'slow' and 'fast' pointers at the head of the list, and move 'fast' two nodes ahead initially.

Traverse the List: Move the 'slow' pointer one step at a time and the 'fast' pointer two steps at a time. Continue this process until the 'fast' pointer reaches the end of the list.

Middle Node Detection: When the 'fast' pointer reaches the end of the list, the 'slow' pointer will be at the node just before the middle node.

Delete Middle Node: Remove the middle node by adjusting the 'next' pointer of the 'slow' node to skip over the middle node.

Return Modified List: Return the head of the modified linked list.

Dry Run

Solution

#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 the middle node of a linked list
    ListNode* deleteMiddle(ListNode* head) {
        /* If the list is empty or has only one node,
         * return NULL as there is no middle node to delete */
        if (head == NULL || head->next == NULL) {
            return NULL;
        }

        // Initialize slow and fast pointers
        ListNode* slow = head;
        ListNode* fast = head;
        fast = head->next->next;

        // Move 'fast' pointer twice as fast as 'slow'
        while (fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
        }

        // Delete the middle node by skipping it
        slow->next = slow->next->next;
        return head;
    }
};

// Function to print the linked list
void printLL(ListNode* head) {
    ListNode* temp = head;
    while (temp != NULL) {
        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;
}
import java.util.*;

// Definition of singly linked list:
class 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 {
    // Function to delete the middle node of a linked list
    public ListNode deleteMiddle(ListNode head) {
        /* If the list is empty or has only one node,
         * return null as there is no middle node to delete */
        if (head == null || head.next == null) {
            return null;
        }

        // Initialize slow and fast pointers
        ListNode slow = head;
        ListNode fast = head.next.next;

        // Move 'fast' pointer twice as fast as 'slow'
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // Delete the middle node by skipping it
        slow.next = slow.next.next;
        return head;
    }

    // Function to print the linked list
    public static void printLL(ListNode head) {
        ListNode temp = head;
        while (temp != null) {
            System.out.print(temp.val + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // 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
        System.out.print("Original Linked List: ");
        printLL(head);

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

        // Displaying the updated linked list
        System.out.print("Updated Linked List: ");
        printLL(head);
    }
}
# Definition of singly linked list:
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    # Function to delete the middle node of a linked list
    def deleteMiddle(self, head):
        """ If the list is empty or has only one node,
        return None as there is no middle node to delete """
        if not head or not head.next:
            return None

        # Initialize slow and fast pointers
        slow = head
        fast = head.next.next

        # Move 'fast' pointer twice as fast as 'slow'
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # Delete the middle node by skipping it
        slow.next = slow.next.next
        return head

# Function to print the linked list
def printLL(head):
    temp = head
    while temp:
        print(temp.val, end=" ")
        temp = temp.next
    print()

# Creating a sample linked list: 
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)

# Display the original linked list
print("Original Linked List: ", end="")
printLL(head)

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

# Displaying the updated linked list
print("Updated Linked List: ", end="")
printLL(head)
// Definition of singly linked list:
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

class Solution {
    // Function to delete the middle node of a linked list
    deleteMiddle(head) {
        /* If the list is empty or has only one node,
         * return null as there is no middle node to delete */
        if (head === null || head.next === null) {
            return null;
        }

        // Initialize slow and fast pointers
        let slow = head;
        let fast = head.next.next;

        // Move 'fast' pointer twice as fast as 'slow'
        while (fast !== null && fast.next !== null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // Delete the middle node by skipping it
        slow.next = slow.next.next;
        return head;
    }
}

// Function to print the linked list
function printLL(head) {
    let temp = head;
    while (temp !== null) {
        process.stdout.write(temp.val + " ");
        temp = temp.next;
    }
    console.log();
}

// Creating a sample linked list: 
let 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
process.stdout.write("Original Linked List: ");
printLL(head);

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

// Displaying the updated linked list
process.stdout.write("Updated Linked List: ");
printLL(head);

Time Complexity

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.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry Run

Solution

Time Complexity

Intuition

Approach

Dry Run

Solution

Time Complexity

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code