Deleting middle node of linked list.
Delete the Middle Node of a Linked List
Problem Description
Given a singly linked list, the task is to delete the middle node. If the list has an even number of nodes, delete the second middle node. For example, given the linked list 1 -> 2 -> 3 -> 4 -> 5, after deletion, it should become 1 -> 2 -> 4 -> 5. If the list is 1 -> 2 -> 3 -> 4, it should become 1 -> 2 -> 4.
Video Explanation
Approach
To delete the middle node of a linked list, we can use the following approach:
-
Find the Length of the List:
- Traverse the list to count the total number of nodes.
-
Determine the Middle Index:
- Calculate the middle index based on whether the length is even or odd.
-
Traverse to the Node Before the Middle:
- Move through the list until reaching the node just before the middle node.
-
Delete the Middle Node:
- Adjust the pointers to bypass the middle node, effectively removing it from the list.
Implementation
Solutions
- C++
- Java
- Python
- JavaScript
#include <iostream>
class Node {
public:
int value;
Node* next;
Node(int val) {
value = val;
next = nullptr;
}
};
class LinkedList {
public:
Node* head;
LinkedList() {
head = nullptr;
}
// Function to delete the middle node
void deleteMiddle() {
if (head == nullptr) return; // If the list is empty
// Step 1: Find the length of the list
int length = 0;
Node* current = head;
while (current != nullptr) {
length++;
current = current->next;
}
// Step 2: Determine the middle index
int middleIndex = length / 2;
// Step 3: Traverse to the node before the middle
current = head;
for (int i = 0; i < middleIndex - 1; i++) {
current = current->next;
}
// Step 4: Delete the middle node
if (current->next != nullptr) {
current->next = current->next->next; // Bypass the middle node
} else {
// If the list has only one node
head = nullptr;
}
}
// Function to add a new node at the end of the list
void append(int value) {
Node* newNode = new Node(value);
if (head == nullptr) {
head = newNode;
return;
}
Node* current = head;
while (current->next != nullptr) {
current = current->next;
}
current->next = newNode;
}
// Function to print the linked list
void printList() {
Node* current = head;
while (current != nullptr) {
std::cout << current->value << " -> ";
current = current->next;
}
std::cout << "nullptr" << std::endl;
}
};
// Example usage
int main() {
LinkedList ll;
ll.append(1);
ll.append(2);
ll.append(3);
ll.append(4);
ll.append(5);
std::cout << "Original Linked List: ";
ll.printList();
ll.deleteMiddle();
std::cout << "Linked List After Deleting Middle Node: ";
ll.printList();
return 0;
}
class Node {
int value;
Node next;
Node(int val) {
this.value = val;
this.next = null;
}
}
class LinkedList {
Node head;
// Function to delete the middle node
public void deleteMiddle() {
if (head == null) return; // If the list is empty
// Step 1: Find the length of the list
int length = 0;
Node current = head;
while (current != null) {
length++;
current = current.next;
}
// Step 2: Determine the middle index
int middleIndex = length / 2;
// Step 3: Traverse to the node before the middle
current = head;
for (int i = 0; i < middleIndex - 1; i++) {
current = current.next;
}
// Step 4: Delete the middle node
if (current.next != null) {
current.next = current.next.next; // Bypass the middle node
} else {
// If the list has only one node
head = null;
}
}
// Function to add a new node at the end of the list
public void append(int value) {
Node newNode = new Node(value);
if (head == null) {
head = newNode;
return;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
// Function to print the linked list
public void printList() {
Node current = head;
while (current != null) {
System.out.print(current.value + " -> ");
current = current.next;
}
System.out.println("null");
}
}
// Example usage
public class Main {
public static void main(String[] args) {
LinkedList ll = new LinkedList();
ll.append(1);
ll.append(2);
ll.append(3);
ll.append(4);
ll.append(5);
System.out.print("Original Linked List: ");
ll.printList();
ll.deleteMiddle();
System.out.print("Linked List After Deleting Middle Node: ");
ll.printList();
}
}
class Node:
def __init__(self, value):
self.value = value
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def delete_middle(self):
if not self.head:
return
# Step 1: Find the length of the list
length = 0
current = self.head
while current:
length += 1
current = current.next
# Step 2: Determine the middle index
middle_index = length // 2
# Step 3: Traverse to the node before the middle
current = self.head
for _ in range(middle_index - 1):
current = current.next
# Step 4: Delete the middle node
if current.next: # If there is a middle node to delete
current.next = current.next.next
def append(self, value):
new_node = Node(value)
if not self.head:
self.head = new_node
return
current = self.head
while current.next:
current = current.next
current.next = new_node
def print_list(self):
current = self.head
while current:
print(current.value, end=" -> ")
current = current.next
print("None")
# Example usage
if __name__ == "__main__":
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.append(4)
ll.append(5)
print("Original Linked List: ")
ll.print_list()
ll.delete_middle()
print("Linked List After Deleting Middle Node: ")
ll.print_list()
var deleteMiddle = function(head) {
if (!head || !head.next) return null;
let slow = head;
let fast = head;
let prev = null;
while (fast && fast.next) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = slow.next;
return head;
};
Track Your Progress
Done with this topic? Mark it as complete to track your progress.
Related Practice Problems
Handpicked problems sharing similar algorithmic topic tags
Medium
#Linked List
Add two numbers represented as linked lists
This document provides a detailed explanation and implementation for adding two numbers represented as linked lists, including step-by-step instructions and example code.
Solve Problem→
Medium
#Linked List
Cloning a Linked List with Random and Next Pointers
Cloning a linked list that contains both next and random pointers involves creating a new linked list that is an exact copy of the original, preserving the structure and relationships of the nodes.
Solve Problem→
Medium
#Linked List
Flattening a linked list involves converting a multi-level linked list into a single-level linked list.
Flattening a linked list involves converting a multi-level linked list into a single-level linked list.
Solve Problem→
💬 Discuss this page
Have a question or spot something confusing in "Deleting middle node of linked list."? Ask below — it's backed by GitHub Discussions, so maintainers get notified like any other GitHub activity.