# Delete Middle of linked list

There is an basic and commonly asked question for in linked list how to delete middle of given linked list in efficient manner. there of many solution of this problem.

We can be solve this problem of many way. first one is very simple approach count all number of linked list nodes and decide which node are exist in middle position. And after that visit middle node closest first node and delete that middle node. This process are tack O(n) time. but in this program there is need of to iterates 2 times of loops.

After Delete Middle node

If you are have deep knowledge of linked list, So we can solve this problem by single loop. In this process firstly need of two pointer variable. One pointer (p1) is initial point of first node of linked list. this pointer are incremented of two times of next linked list node, So this is fast pointer. And other pointer (p2) is slowly increment by one by one.

That means p1 and p2 is incremented by this p1->next->next and p2->next . When p1->next and p1->next->next are NULL so p2 are point to is pointed to middle of linked list. So we can remove linked list element by using of single loop. In below program is implemented solutions.

``````/*
C program for
*/
#include <stdio.h>
#include <stdlib.h>

{
int data;
};
struct SingleLL
{
};
// Returns the new linked list
{
// Create memory of head and tail Nodes
struct SingleLL *sll = (struct SingleLL *)
malloc(sizeof(struct SingleLL));
if (sll == NULL)
{
printf("Memory overflow\n");
}
else
{
}
return sll;
}
// Handles the request of adding new node at beginning of linked list
void addNode(struct SingleLL *sll, int data)
{
// Create dynamic node
if (node == NULL)
{
return;
}
else
{
// Set initial node value
node->data = data;
}
}
{
if (node == NULL)
{
return;
}
while (temp != NULL)
{
// Display node value
printf(" %d →", temp->data);
// Visit to next node
temp = temp->next;
}
printf(" NULL\n");
}
// Delete the middle node of linked list
{
{
// When linked list are no elements
}
else if (head->next == NULL &&
{
// When linked list are less than  of 3 nodes
printf("\nLess then 3 node of linked list\n");
}
else
{
// Find the middle and its previous node
while (temp != NULL &&
temp->next != NULL &&
temp->next->next != NULL)
{
if (midPrevious == NULL)
{
// When first node
midPrevious = temp;
}
else
{
// Visit to next node
midPrevious = midPrevious->next;
}
// Visit to next second next node
temp = temp->next->next;
}
// Get the node which is deleting
temp = midPrevious->next;
// Show deleted node
printf("Delete node : %d\n", temp->data);
midPrevious->next = temp->next;
free(temp);
}
}
int main(int argc, char
const *argv[])
{
// 7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
printf("Before Delete middle node\n");

printf("After Delete middle node\n");
return 0;
}``````

#### Output

`````` Linked List
7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
Before Delete middle node
7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
Delete node : 4
After Delete middle node
7 → 6 → 5 → 3 → 2 → 1 → NULL``````
``````/*
Java program for
Delete middle node of linked list
*/
{
public int data;
{
this.data = data;
this.next = null;
}
}
public class SingleLL
{
public SingleLL()
{
}
{
// Create new node
// Connect current node to previous head
}
public void display()
{
{
return;
}
while (temp != null)
{
// Display node value
System.out.print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
System.out.print(" NULL\n");
}
// Delete the middle node of linked list
public void deleteMid()
{
{
// When linked list are no elements
}
else if (this.head.next == null &&
{
// When linked list are less than  of 3 nodes
System.out.println("Less then 3 node of linked list");
}
else
{
// Find the middle and its previous node
while (temp != null &&
temp.next != null &&
temp.next.next != null)
{
if (midPrevious == null)
{
// When first node
midPrevious = temp;
}
else
{
// Visit to next node
midPrevious = midPrevious.next;
}
// Visit to next second next node
temp = temp.next.next;
}
// Get the node which is deleting
temp = midPrevious.next;
// Show deleted node
System.out.println("Delete node : " + temp.data);
midPrevious.next = temp.next;
}
}
public static void main(String[] args)
{
SingleLL sll = new SingleLL();
// 7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
System.out.println("Before Delete middle node");
sll.display();
// Delete middle node
sll.deleteMid();
System.out.println("After Delete middle node");
sll.display();
}
}``````

#### Output

``````Before Delete middle node
7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
Delete node : 4
After Delete middle node
7 → 6 → 5 → 3 → 2 → 1 → NULL``````
``````// Include header file
#include <iostream>

using namespace std;
/*
C++ program for
Delete middle node of linked list
*/
{
public: int data;
{
this->data = data;
this->next = NULL;
}
};
class SingleLL
{
SingleLL()
{
}
{
// Create new node
// Connect current node to previous head
}
void display()
{
{
return;
}
while (temp != NULL)
{
// Display node value
cout << " " << temp->data << " →";
// Visit to next node
temp = temp->next;
}
cout << " NULL\n";
}
// Delete the middle node of linked list
void deleteMid()
{
{
// When linked list are no elements
cout << "Empty Linked List" << endl;
}
else if (this->head->next == NULL &&
{
// When linked list are less than  of 3 nodes
cout << "Less then 3 node of linked list" << endl;
}
else
{
// Find the middle and its previous node
while (temp != NULL &&
temp->next != NULL &&
temp->next->next != NULL)
{
if (midPrevious == NULL)
{
// When first node
midPrevious = temp;
}
else
{
// Visit to next node
midPrevious = midPrevious->next;
}
// Visit to next second next node
temp = temp->next->next;
}
// Get the node which is deleting
temp = midPrevious->next;
// Show deleted node
cout << "Delete node : " << temp->data << endl;
midPrevious->next = temp->next;

delete temp;
}
}
};
int main()
{
SingleLL *sll = new SingleLL();
// 7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
cout << "Before Delete middle node" << endl;
sll->display();
// Delete middle node
sll->deleteMid();
cout << "After Delete middle node" << endl;
sll->display();
return 0;
}``````

#### Output

``````Before Delete middle node
7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
Delete node : 4
After Delete middle node
7 → 6 → 5 → 3 → 2 → 1 → NULL``````
``````package main
import "fmt"
/*
Go program for
Delete middle node of linked list
*/
data int
}
me.data = data
me.next = nil
return me
}
type SingleLL struct {
}
func getSingleLL() * SingleLL {
var me *SingleLL = &SingleLL {}
return me
}
// Create new node
// Connect current node to previous head
}
func(this SingleLL) display() {
return
}
for (temp != nil) {
// Display node value
fmt.Print(" ", temp.data, " →")
// Visit to next node
temp = temp.next
}
fmt.Print(" NULL\n")
}
// Delete the middle node of linked list
func(this SingleLL) deleteMid() {
// When linked list are no elements
} else if this.head.next == nil &&
// When linked list are less than  of 3 nodes
fmt.Println("Less then 3 node of linked list")
} else {
var midPrevious * LinkNode = nil
// Find the middle and its previous node
for (temp != nil &&
temp.next != nil &&
temp.next.next != nil) {
if midPrevious == nil {
// When first node
midPrevious = temp
} else {
// Visit to next node
midPrevious = midPrevious.next
}
// Visit to next second next node
temp = temp.next.next
}
// Get the node which is deleting
temp = midPrevious.next
// Show deleted node
fmt.Println("Delete node : ", temp.data)
midPrevious.next = temp.next
}
}
func main() {
var sll * SingleLL = getSingleLL()
// 7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
fmt.Println("Before Delete middle node")
sll.display()
// Delete middle node
sll.deleteMid()
fmt.Println("After Delete middle node")
sll.display()
}``````

#### Output

``````Before Delete middle node
7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
Delete node : 4
After Delete middle node
7 → 6 → 5 → 3 → 2 → 1 → NULL``````
``````// Include namespace system
using System;
/*
Csharp program for
Delete middle node of linked list
*/
{
public int data;
{
this.data = data;
this.next = null;
}
}
public class SingleLL
{
public SingleLL()
{
}
{
// Create new node
// Connect current node to previous head
}
public void display()
{
{
return;
}
while (temp != null)
{
// Display node value
Console.Write(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
Console.Write(" NULL\n");
}
// Delete the middle node of linked list
public void deleteMid()
{
{
// When linked list are no elements
}
{
// When linked list are less than  of 3 nodes
Console.WriteLine("Less then 3 node of linked list");
}
else
{
// Find the middle and its previous node
while (temp != null && temp.next != null && temp.next.next != null)
{
if (midPrevious == null)
{
// When first node
midPrevious = temp;
}
else
{
// Visit to next node
midPrevious = midPrevious.next;
}
// Visit to next second next node
temp = temp.next.next;
}
// Get the node which is deleting
temp = midPrevious.next;
// Show deleted node
Console.WriteLine("Delete node : " + temp.data);
midPrevious.next = temp.next;
}
}
public static void Main(String[] args)
{
SingleLL sll = new SingleLL();
// 7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
Console.WriteLine("Before Delete middle node");
sll.display();
// Delete middle node
sll.deleteMid();
Console.WriteLine("After Delete middle node");
sll.display();
}
}``````

#### Output

``````Before Delete middle node
7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
Delete node : 4
After Delete middle node
7 → 6 → 5 → 3 → 2 → 1 → NULL``````
``````<?php
/*
Php program for
Delete middle node of linked list
*/
{
public \$data;
public \$next;
public  function __construct(\$data)
{
\$this->data = \$data;
\$this->next = NULL;
}
}
class SingleLL
{
public  function __construct()
{
}
{
// Create new node
// Connect current node to previous head
}
public  function display()
{
{
return;
}
while (\$temp != NULL)
{
// Display node value
echo(" ".strval(\$temp->data).
" →");
// Visit to next node
\$temp = \$temp->next;
}
echo(" NULL\n");
}
// Delete the middle node of linked list
public  function deleteMid()
{
{
// When linked list are no elements
"\n");
}
{
// When linked list are less than  of 3 nodes
echo("Less then 3 node of linked list".
"\n");
}
else
{
\$midPrevious = NULL;
// Find the middle and its previous node
while (\$temp != NULL && \$temp->next != NULL && \$temp->next->next != NULL)
{
if (\$midPrevious == NULL)
{
// When first node
\$midPrevious = \$temp;
}
else
{
// Visit to next node
\$midPrevious = \$midPrevious->next;
}
// Visit to next second next node
\$temp = \$temp->next->next;
}
// Get the node which is deleting
\$temp = \$midPrevious->next;
// Show deleted node
echo("Delete node : ".strval(\$temp->data).
"\n");
\$midPrevious->next = \$temp->next;
}
}
}

function main()
{
\$sll = new SingleLL();
// 7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
echo("Before Delete middle node".
"\n");
\$sll->display();
// Delete middle node
\$sll->deleteMid();
echo("After Delete middle node".
"\n");
\$sll->display();
}
main();``````

#### Output

``````Before Delete middle node
7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
Delete node : 4
After Delete middle node
7 → 6 → 5 → 3 → 2 → 1 → NULL``````
``````/*
Node JS program for
Delete middle node of linked list
*/
{
constructor(data)
{
this.data = data;
this.next = null;
}
}
class SingleLL
{
constructor()
{
}
{
// Create new node
// Connect current node to previous head
}
display()
{
{
return;
}
while (temp != null)
{
// Display node value
process.stdout.write(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
process.stdout.write(" NULL\n");
}
// Delete the middle node of linked list
deleteMid()
{
{
// When linked list are no elements
}
else if (this.head.next == null &&
{
// When linked list are less than  of 3 nodes
console.log("Less then 3 node of linked list");
}
else
{
var midPrevious = null;
// Find the middle and its previous node
while (temp != null &&
temp.next != null &&
temp.next.next != null)
{
if (midPrevious == null)
{
// When first node
midPrevious = temp;
}
else
{
// Visit to next node
midPrevious = midPrevious.next;
}
// Visit to next second next node
temp = temp.next.next;
}
// Get the node which is deleting
temp = midPrevious.next;
// Show deleted node
console.log("Delete node : " + temp.data);
midPrevious.next = temp.next;
}
}
}

function main()
{
var sll = new SingleLL();
// 7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
console.log("Before Delete middle node");
sll.display();
// Delete middle node
sll.deleteMid();
console.log("After Delete middle node");
sll.display();
}
main();``````

#### Output

``````Before Delete middle node
7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
Delete node : 4
After Delete middle node
7 → 6 → 5 → 3 → 2 → 1 → NULL``````
``````#    Python 3 program for
#    Delete middle node of linked list

def __init__(self, data) :
self.data = data
self.next = None

class SingleLL :
def __init__(self) :

#  Create new node
#  Connect current node to previous head

def display(self) :
return

while (temp != None) :
#  Display node value
print("", temp.data ,"→", end = "")
#  Visit to next node
temp = temp.next

print(" NULL")

#  Delete the middle node of linked list
def deleteMid(self) :
#  When linked list are no elements
#  When linked list are less than  of 3 nodes
print("Less then 3 node of linked list")
else :
midPrevious = None
#  Find the middle and its previous node
while (temp != None and temp.next != None and temp.next.next != None) :
if (midPrevious == None) :
#  When first node
midPrevious = temp
else :
#  Visit to next node
midPrevious = midPrevious.next

#  Visit to next second next node
temp = temp.next.next

#  Get the node which is deleting
temp = midPrevious.next
#  Show deleted node
print("Delete node : ", temp.data)
midPrevious.next = temp.next

def main() :
sll = SingleLL()
#  7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
print("Before Delete middle node")
sll.display()
#  Delete middle node
sll.deleteMid()
print("After Delete middle node")
sll.display()

if __name__ == "__main__": main()``````

#### Output

``````Before Delete middle node
7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
Delete node :  4
After Delete middle node
7 → 6 → 5 → 3 → 2 → 1 → NULL``````
``````#    Ruby program for
#    Delete middle node of linked list

attr_accessor :data, :next
def initialize(data)
self.data = data
self.next = nil
end

end

class SingleLL
# Define the accessor and reader of class SingleLL
def initialize()
end

#  Create new node
#  Connect current node to previous head
end

def display()
return
end

while (temp != nil)
#  Display node value
print(" ", temp.data ," →")
#  Visit to next node
temp = temp.next
end

print(" NULL\n")
end

#  Delete the middle node of linked list
def deleteMid()
#  When linked list are no elements
#  When linked list are less than  of 3 nodes
print("Less then 3 node of linked list", "\n")
else

midPrevious = nil
#  Find the middle and its previous node
while (temp != nil && temp.next != nil && temp.next.next != nil)
if (midPrevious == nil)
#  When first node
midPrevious = temp
else

#  Visit to next node
midPrevious = midPrevious.next
end

#  Visit to next second next node
temp = temp.next.next
end

#  Get the node which is deleting
temp = midPrevious.next
#  Show deleted node
print("Delete node : ", temp.data, "\n")
midPrevious.next = temp.next
end

end

end

def main()
sll = SingleLL.new()
#  7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
print("Before Delete middle node", "\n")
sll.display()
#  Delete middle node
sll.deleteMid()
print("After Delete middle node", "\n")
sll.display()
end

main()``````

#### Output

``````Before Delete middle node
7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
Delete node : 4
After Delete middle node
7 → 6 → 5 → 3 → 2 → 1 → NULL
``````
``````/*
Scala program for
Delete middle node of linked list
*/
{
def this(data: Int)
{
this(data, null);
}
}
{
def this()
{
this(null);
}
def addNode(data: Int): Unit = {
// Create new node
// Connect current node to previous head
}
def display(): Unit = {
{
return;
}
while (temp != null)
{
// Display node value
print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
print(" NULL\n");
}
// Delete the middle node of linked list
def deleteMid(): Unit = {
{
// When linked list are no elements
}
else if (this.head.next == null &&
{
// When linked list are less than  of 3 nodes
println("Less then 3 node of linked list");
}
else
{
// Find the middle and its previous node
while (temp != null &&
temp.next != null &&
temp.next.next != null)
{
if (midPrevious == null)
{
// When first node
midPrevious = temp;
}
else
{
// Visit to next node
midPrevious = midPrevious.next;
}
// Visit to next second next node
temp = temp.next.next;
}
// Get the node which is deleting
temp = midPrevious.next;
// Show deleted node
println("Delete node : " + temp.data);
midPrevious.next = temp.next;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var sll: SingleLL = new SingleLL();
// 7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
println("Before Delete middle node");
sll.display();
// Delete middle node
sll.deleteMid();
println("After Delete middle node");
sll.display();
}
}``````

#### Output

``````Before Delete middle node
7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
Delete node : 4
After Delete middle node
7 → 6 → 5 → 3 → 2 → 1 → NULL``````
``````/*
Swift 4 program for
Delete middle node of linked list
*/
{
var data: Int;
init(_ data: Int)
{
self.data = data;
self.next = nil;
}
}
class SingleLL
{
init()
{
}
{
// Create new node
// Connect current node to previous head
}
func display()
{
{
return;
}
while (temp  != nil)
{
// Display node value
print("", temp!.data ,"→", terminator: "");
// Visit to next node
temp = temp!.next;
}
print(" NULL");
}
// Delete the middle node of linked list
func deleteMid()
{
{
// When linked list are no elements
}
else if (self.head!.next == nil &&
{
// When linked list are less than  of 3 nodes
print("Less then 3 node of linked list");
}
else
{
// Find the middle and its previous node
while (temp  != nil && temp!.next  != nil &&
temp!.next!.next  != nil)
{
if (midPrevious == nil)
{
// When first node
midPrevious = temp;
}
else
{
// Visit to next node
midPrevious = midPrevious!.next;
}
// Visit to next second next node
temp = temp!.next!.next;
}
// Get the node which is deleting
temp = midPrevious!.next;
// Show deleted node
print("Delete node : ", temp!.data);
midPrevious!.next = temp!.next;
}
}
}
func main()
{
let sll: SingleLL = SingleLL();
// 7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
print("Before Delete middle node");
sll.display();
// Delete middle node
sll.deleteMid();
print("After Delete middle node");
sll.display();
}
main();``````

#### Output

``````Before Delete middle node
7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
Delete node :  4
After Delete middle node
7 → 6 → 5 → 3 → 2 → 1 → NULL``````
``````/*
Kotlin program for
Delete middle node of linked list
*/
{
var data: Int;
constructor(data: Int)
{
this.data = data;
this.next = null;
}
}
class SingleLL
{
constructor()
{
}
{
// Create new node
// Connect current node to previous head
}
fun display(): Unit
{
{
return;
}
while (temp != null)
{
// Display node value
print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
print(" NULL\n");
}
// Delete the middle node of linked list
fun deleteMid(): Unit
{
{
// When linked list are no elements
}
{
// When linked list are less than  of 3 nodes
println("Less then 3 node of linked list");
}
else
{
var midPrevious: LinkNode ? = null;
// Find the middle and its previous node
while (temp != null && temp.next != null &&
temp.next?.next != null)
{
if (midPrevious == null)
{
// When first node
midPrevious = temp;
}
else
{
// Visit to next node
midPrevious = midPrevious.next;
}
// Visit to next second next node
temp = temp.next?.next;
}
// Get the node which is deleting
temp = midPrevious?.next;
// Show deleted node
println("Delete node : " + temp!!.data);
midPrevious?.next = temp.next;
}
}
}
fun main(args: Array < String > ): Unit
{
val sll: SingleLL = SingleLL();
// 7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
println("Before Delete middle node");
sll.display();
// Delete middle node
sll.deleteMid();
println("After Delete middle node");
sll.display();
}``````

#### Output

``````Before Delete middle node
7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
Delete node : 4
After Delete middle node
7 → 6 → 5 → 3 → 2 → 1 → NULL``````

Note that in this linked list are 7 nodes. Then so 4'th position nodes is middle node of this linked list.

## Conclusion

This program are working when linked list contain at least three nodes. because if node are less than 3 then there are not possible to find mid node.

And linked list are contain even number of nodes. assuming there are more than two nodes. Then in this case there are possible two middle nodes. Let take an example.

`` 1-->2-->3-->4-->5-->6-->NULL ``

In this situation have 3rd and 4th position nodes are same priority of the mid position. So in this case both algorithm are valid to delete middle of 3rd position or 4th position nodes.

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.