# Insert node at middle of linked list

Linked list are useful data structure, If you are hold the reference of front and rear by pointer then possible to get that element directly. Otherwise there are not possible to get random position elements.

That reason there is most asking question are, how to insert node at middle of given linked list. Normally there are two solution of this problem.

First method : counting all linked list node using one traversal. So we are know about exectly, how many node are exist in this linked list. And in a second traversal start to head and iterative loop are (count/2) times and get middle node. And insert new node to that position (modifying of pointer position when inserted node).

That is basic method you can try this approach. This process time complexity is O(n). But note that in this approach every node at almost 2 times are have traversal. Next method are do this task in single traversal.

Method two: Use two pointer (temp,middle) both are assigning the value of head pointer reference. visited of temp pointer are (temp->next->next) two times when temp are not NULL and temp->next are not NULL and temp->next->next not NULL. Respective to visit middle pointer to (middle->next). When temp is NULL or temp->next==NULL and temp->next->next are NULL then terminated the loop. And help of middle pointer add new node to middle position.

Suppose we are inserted the following (1, 2, 3, 4, 5, 6, 7) node in a sequence. In this post are implement second approach.

Here given code implementation process.

``````// Java Program for
// Insert linked list element at middle position

// Linked list node
{
public int data;
{
this.data = data;
this.next = null;
}
}
{
//Class constructors
{
}
//insert  element
public void insert(int value)
{
// Create a new node
if (this.head == null)
{
}
else
{
// find middle node
while (temp.next != null && temp.next.next != null)
{
temp = temp.next.next;
middle = middle.next;
}
node.next = middle.next;
middle.next = node;
}
}
// Display linked list element
public void display()
{
if (this.head == null)
{
return;
}
// iterating linked list elements
while (temp != null)
{
System.out.print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
System.out.print(" NULL\n");
}
public static void main(String[] args)
{
sll.insert(1);
sll.insert(2);
sll.insert(3);
sll.insert(4);
sll.insert(5);
sll.insert(6);
sll.insert(7);
// 1 → 3 → 5 → 7 → 6 → 4 → 2 → NULL
sll.display();
}
}``````

#### Output

`` 1 → 3 → 5 → 7 → 6 → 4 → 2 → NULL``
``````// C Program for
// Insert linked list node at middle of linked list
#include <stdio.h>
#include <stdlib.h>

{
int data;
};
// Singly linked list
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 middle of linked list
void addNode(struct SingleLL *sll, int data)
{
// Create dynamic node
struct LinkNode *node = (struct LinkNode *)
if (node == NULL)
{
printf("Memory overflow to Create LinkNode\n");
return;
}
else
{
// Set initial node value
node->data = data;
node->next = NULL;
}
if (sll->head == NULL)
{
}
else
{
while (temp && temp->next != NULL && temp->next->next != NULL)
{
temp = temp->next->next;
middle = middle->next;
}
// Insert node into the middle of the linked list
node->next = middle->next;
middle->next = node;
}
}
// Display linked list element
void display(struct LinkNode *node)
{
if (node == NULL)
{
return;
}
struct LinkNode *temp = node;
// iterating linked list elements
while (temp != NULL)
{
printf(" %d →", temp->data);
// Visit to next node
temp = temp->next;
}
printf(" NULL\n");
}
int main()
{
struct SingleLL *sll = newLinkedList();
//insert element of linked list
//display all node
return 0;
}``````

#### Output

`` 1 → 3 → 5 → 7 → 6 → 4 → 2 → NULL``
``````// Include header file
#include <iostream>
using namespace std;
// C++ Program for
// Insert linked list element at middle

// Linked list node
{
public: int data;
{
this->data = data;
this->next = NULL;
}
};
{
{
}
// Add node at middle position of linked list
void insert(int value)
{
// Create a new node
if (this->head == NULL)
{
}
else
{
// find middle node
while (temp->next != NULL && temp->next->next != NULL)
{
temp = temp->next->next;
middle = middle->next;
}
node->next = middle->next;
middle->next = node;
}
}
// Display linked list element
void display()
{
if (this->head == NULL)
{
return;
}
// iterating linked list elements
while (temp != NULL)
{
cout << " " << temp->data << " →";
// Visit to next node
temp = temp->next;
}
cout << " NULL\n";
}
};
int main()
{
sll->insert(1);
sll->insert(2);
sll->insert(3);
sll->insert(4);
sll->insert(5);
sll->insert(6);
sll->insert(7);
// 1 → 3 → 5 → 7 → 6 → 4 → 2 → NULL
sll->display();
return 0;
}``````

#### Output

`` 1 → 3 → 5 → 7 → 6 → 4 → 2 → NULL``
``````package main
import "fmt"
// Go Program for
// Insert linked list element at middle

// Linked list node
type LinkNode struct {
data int
}
me.data = data
me.next = nil
return me
}
type LinkedList struct {
}
return me
}
// Add node at middle position of linked list
func(this *LinkedList) insert(value int) {
// Create a new node
if this.head == nil {
} else {
// find middle node
for (temp.next != nil && temp.next.next != nil) {
temp = temp.next.next
middle = middle.next
}
node.next = middle.next
middle.next = node
}
}
// Display linked list element
func(this LinkedList) display() {
if this.head == nil {
return
}
// iterating linked list elements
for (temp != nil) {
fmt.Print(" ", temp.data, " →")
// Visit to next node
temp = temp.next
}
fmt.Print(" NULL\n")
}
func main() {
sll.insert(1)
sll.insert(2)
sll.insert(3)
sll.insert(4)
sll.insert(5)
sll.insert(6)
sll.insert(7)
// 1 → 3 → 5 → 7 → 6 → 4 → 2 → NULL
sll.display()
}``````

#### Output

`` 1 → 3 → 5 → 7 → 6 → 4 → 2 → NULL``
``````// Include namespace system
using System;
// Csharp Program for
// Insert linked list element at middle

// Linked list node
{
public int data;
{
this.data = data;
this.next = null;
}
}
{
{
}
// Add node at middle position of linked list
public void insert(int value)
{
// Create a new node
if (this.head == null)
{
}
else
{
// find middle node
while (temp.next != null && temp.next.next != null)
{
temp = temp.next.next;
middle = middle.next;
}
node.next = middle.next;
middle.next = node;
}
}
// Display linked list element
public void display()
{
if (this.head == null)
{
return;
}
// iterating linked list elements
while (temp != null)
{
Console.Write(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
Console.Write(" NULL\n");
}
public static void Main(String[] args)
{
sll.insert(1);
sll.insert(2);
sll.insert(3);
sll.insert(4);
sll.insert(5);
sll.insert(6);
sll.insert(7);
// 1 → 3 → 5 → 7 → 6 → 4 → 2 → NULL
sll.display();
}
}``````

#### Output

`` 1 → 3 → 5 → 7 → 6 → 4 → 2 → NULL``
``````<?php
// Php Program for
// Insert linked list element at middle

// Linked list node
{
public \$data;
public \$next;
public  function __construct(\$data)
{
\$this->data = \$data;
\$this->next = NULL;
}
}
{
public  function __construct()
{
}
// Add node at middle position of linked list
public  function insert(\$value)
{
// Create a new node
\$node = new LinkNode(\$value);
if (\$this->head == NULL)
{
}
else
{
// find middle node
while (\$temp->next != NULL && \$temp->next->next != NULL)
{
\$temp = \$temp->next->next;
\$middle = \$middle->next;
}
\$node->next = \$middle->next;
\$middle->next = \$node;
}
}
// Display linked list element
public  function display()
{
if (\$this->head == NULL)
{
return;
}
// iterating linked list elements
while (\$temp != NULL)
{
echo(" ".\$temp->data.
" →");
// Visit to next node
\$temp = \$temp->next;
}
echo(" NULL\n");
}
}

function main()
{
\$sll = new LinkedList();
\$sll->insert(1);
\$sll->insert(2);
\$sll->insert(3);
\$sll->insert(4);
\$sll->insert(5);
\$sll->insert(6);
\$sll->insert(7);
// 1 → 3 → 5 → 7 → 6 → 4 → 2 → NULL
\$sll->display();
}
main();``````

#### Output

`` 1 → 3 → 5 → 7 → 6 → 4 → 2 → NULL``
``````// Node JS Program for
// Insert linked list element at middle

// Linked list node
{
constructor(data)
{
this.data = data;
this.next = null;
}
}
{
constructor()
{
}
// Add node at middle position of linked list
insert(value)
{
// Create a new node
var node = new LinkNode(value);
if (this.head == null)
{
}
else
{
var temp = this.head;
var middle = this.head;
// find middle node
while (temp.next != null && temp.next.next != null)
{
temp = temp.next.next;
middle = middle.next;
}
node.next = middle.next;
middle.next = node;
}
}
// Display linked list element
display()
{
if (this.head == null)
{
return;
}
var temp = this.head;
// iterating linked list elements
while (temp != null)
{
process.stdout.write(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
process.stdout.write(" NULL\n");
}
}

function main()
{
var sll = new LinkedList();
sll.insert(1);
sll.insert(2);
sll.insert(3);
sll.insert(4);
sll.insert(5);
sll.insert(6);
sll.insert(7);
// 1 → 3 → 5 → 7 → 6 → 4 → 2 → NULL
sll.display();
}
main();``````

#### Output

`` 1 → 3 → 5 → 7 → 6 → 4 → 2 → NULL``
``````#  Python 3 Program for
#  Insert linked list element at middle

#  Linked list node
def __init__(self, data) :
self.data = data
self.next = None

def __init__(self) :

#  Add node at middle position of linked list
def insert(self, value) :
#  Create a new node
if (self.head == None) :
else :
#  find middle node
while (temp.next != None and temp.next.next != None) :
temp = temp.next.next
middle = middle.next

node.next = middle.next
middle.next = node

#  Display linked list element
def display(self) :
if (self.head == None) :
return

#  iterating linked list elements
while (temp != None) :
print("", temp.data ,"→", end = "")
#  Visit to next node
temp = temp.next

print(" NULL")

def main() :
sll.insert(1)
sll.insert(2)
sll.insert(3)
sll.insert(4)
sll.insert(5)
sll.insert(6)
sll.insert(7)
#  1 → 3 → 5 → 7 → 6 → 4 → 2 → NULL
sll.display()

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

#### Output

`` 1 → 3 → 5 → 7 → 6 → 4 → 2 → NULL``
``````#  Ruby Program for
#  Insert linked list element at middle

#  Linked list node
# Define the accessor and reader of class LinkNode
attr_accessor :data, :next
def initialize(data)
self.data = data
self.next = nil
end

end

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

#  Add node at middle position of linked list
def insert(value)
#  Create a new node
if (self.head == nil)
else

#  find middle node
while (temp.next != nil && temp.next.next != nil)
temp = temp.next.next
middle = middle.next
end

node.next = middle.next
middle.next = node
end

end

#  Display linked list element
def display()
if (self.head == nil)
return
end

#  iterating linked list elements
while (temp != nil)
print(" ", temp.data ," →")
#  Visit to next node
temp = temp.next
end

print(" NULL\n")
end

end

def main()
sll.insert(1)
sll.insert(2)
sll.insert(3)
sll.insert(4)
sll.insert(5)
sll.insert(6)
sll.insert(7)
#  1 → 3 → 5 → 7 → 6 → 4 → 2 → NULL
sll.display()
end

main()``````

#### Output

`````` 1 → 3 → 5 → 7 → 6 → 4 → 2 → NULL
``````
``````// Scala Program for
// Insert linked list element at middle

// Linked list node
class LinkNode(var data: Int,
{
def this(data: Int)
{
this(data, null);
}
}
{
def this()
{
this(null);
}
// Add node at middle position of linked list
def insert(value: Int): Unit = {
// Create a new node
if (this.head == null)
{
}
else
{
// find middle node
while (temp.next != null && temp.next.next != null)
{
temp = temp.next.next;
middle = middle.next;
}
node.next = middle.next;
middle.next = node;
}
}
// Display linked list element
def display(): Unit = {
if (this.head == null)
{
return;
}
// iterating linked list elements
while (temp != null)
{
print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
print(" NULL\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
sll.insert(1);
sll.insert(2);
sll.insert(3);
sll.insert(4);
sll.insert(5);
sll.insert(6);
sll.insert(7);
// 1 → 3 → 5 → 7 → 6 → 4 → 2 → NULL
sll.display();
}
}``````

#### Output

`` 1 → 3 → 5 → 7 → 6 → 4 → 2 → NULL``
``````// Swift 4 Program for
// Insert linked list element at middle

// Linked list node
{
var data: Int;
var next: LinkNode? ;
init(_ data: Int)
{
self.data = data;
self.next = nil;
}
}
{
init()
{
}
// Add node at middle position of linked list
func insert(_ value: Int)
{
// Create a new node
if (self.head == nil)
{
}
else
{
// find middle node
while (temp!.next  != nil && temp!.next!.next  != nil)
{
temp = temp!.next!.next;
middle = middle!.next;
}
node.next = middle!.next;
middle!.next = node;
}
}
// Display linked list element
func display()
{
if (self.head == nil)
{
return;
}
// iterating linked list elements
while (temp  != nil)
{
print("", temp!.data ,"→", terminator: "");
// Visit to next node
temp = temp!.next;
}
print(" NULL");
}
}
func main()
{
sll.insert(1);
sll.insert(2);
sll.insert(3);
sll.insert(4);
sll.insert(5);
sll.insert(6);
sll.insert(7);
// 1 → 3 → 5 → 7 → 6 → 4 → 2 → NULL
sll.display();
}
main();``````

#### Output

`` 1 → 3 → 5 → 7 → 6 → 4 → 2 → NULL``
``````// Kotlin Program for
// Insert linked list element at middle

// Linked list node
{
var data: Int;
var next: LinkNode ? ;
constructor(data: Int)
{
this.data = data;
this.next = null;
}
}
{
constructor()
{
}
// Add node at middle position of linked list
fun insert(value: Int): Unit
{
// Create a new node
if (this.head == null)
{
}
else
{
// find middle node
while (temp?.next != null && temp.next?.next != null)
{
temp = temp.next?.next;
middle = middle?.next;
}
node.next = middle?.next;
middle?.next = node;
}
}
// Display linked list element
fun display(): Unit
{
if (this.head == null)
{
return;
}
// iterating linked list elements
while (temp != null)
{
print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
print(" NULL\n");
}
}
fun main(args: Array < String > ): Unit
{
sll.insert(1);
sll.insert(2);
sll.insert(3);
sll.insert(4);
sll.insert(5);
sll.insert(6);
sll.insert(7);
// 1 → 3 → 5 → 7 → 6 → 4 → 2 → NULL
sll.display();
}``````

#### Output

`` 1 → 3 → 5 → 7 → 6 → 4 → 2 → NULL``

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.