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.

insert linked list node in middle position

Here given code implementation process.

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

// Linked list node
class LinkNode
{
    public int data;
    public LinkNode next;
    public LinkNode(int data)
    {
        this.data = data;
        this.next = null;
    }
}
public class LinkedList
{
    public LinkNode head;
    //Class constructors
    public LinkedList()
    {
        this.head = null;
    }
    //insert  element
    public void insert(int value)
    {
        // Create a new node
        LinkNode node = new LinkNode(value);
        if (this.head == null)
        {
            this.head = node;
        }
        else
        {
            LinkNode temp = this.head;
            LinkNode middle = this.head;
            // find middle node
            while (temp.next != null && temp.next.next != null)
            {
                temp = temp.next.next;
                middle = middle.next;
            }
            // add node
            node.next = middle.next;
            middle.next = node;
        }
    }
    // Display linked list element
    public void display()
    {
        if (this.head == null)
        {
            return;
        }
        LinkNode temp = this.head;
        // 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)
    {
        LinkedList sll = new LinkedList();
        // Add node
        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
java insert linked list node in middle position
// C Program for
// Insert linked list node at middle of linked list
#include <stdio.h>
#include <stdlib.h>

// Linked List LinkNode
struct LinkNode
{
    int data;
    struct LinkNode *next;
};
// Singly linked list 
struct SingleLL
{
    struct LinkNode *head;
};
// Returns the new linked list
struct SingleLL *newLinkedList()
{
    // Create memory of head and tail Nodes
    struct SingleLL *sll = (struct SingleLL *)
    malloc(sizeof(struct SingleLL));
    if (sll == NULL)
    {
        printf("Memory overflow\n");
    }
    else
    {
        sll->head = NULL;
    }
    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 *)
    malloc(sizeof(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)
    {
        sll->head = node;
    }
    else
    {
        struct LinkNode *temp = sll->head;
        struct LinkNode *middle = sll->head;
        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
    addNode(sll, 1);
    addNode(sll, 2);
    addNode(sll, 3);
    addNode(sll, 4);
    addNode(sll, 5);
    addNode(sll, 6);
    addNode(sll, 7);
    //display all node
    display(sll->head);
    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
class LinkNode
{
    public: int data;
    LinkNode *next;
    LinkNode(int data)
    {
        this->data = data;
        this->next = NULL;
    }
};
class LinkedList
{
    public: LinkNode *head;
    LinkedList()
    {
        this->head = NULL;
    }
    // Add node at middle position of linked list
    void insert(int value)
    {
        // Create a new node
        LinkNode *node = new LinkNode(value);
        if (this->head == NULL)
        {
            this->head = node;
        }
        else
        {
            LinkNode *temp = this->head;
            LinkNode *middle = this->head;
            // find middle node
            while (temp->next != NULL && temp->next->next != NULL)
            {
                temp = temp->next->next;
                middle = middle->next;
            }
            // add node
            node->next = middle->next;
            middle->next = node;
        }
    }
    // Display linked list element
    void display()
    {
        if (this->head == NULL)
        {
            return;
        }
        LinkNode *temp = this->head;
        // iterating linked list elements
        while (temp != NULL)
        {
            cout << " " << temp->data << " →";
            // Visit to next node
            temp = temp->next;
        }
        cout << " NULL\n";
    }
};
int main()
{
    LinkedList *sll = new LinkedList();
    // Add node
    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
    next * LinkNode
}
func getLinkNode(data int) * LinkNode {
    var me *LinkNode = &LinkNode {}
    me.data = data
    me.next = nil
    return me
}
type LinkedList struct {
    head * LinkNode
}
func getLinkedList() * LinkedList {
    var me *LinkedList = &LinkedList {}
    me.head = nil
    return me
}
// Add node at middle position of linked list
func(this *LinkedList) insert(value int) {
    // Create a new node
    var node * LinkNode = getLinkNode(value)
    if this.head == nil {
        this.head = node
    } else {
        var temp * LinkNode = this.head
        var middle * LinkNode = this.head
        // find middle node
        for (temp.next != nil && temp.next.next != nil) {
            temp = temp.next.next
            middle = middle.next
        }
        // add node
        node.next = middle.next
        middle.next = node
    }
}
// Display linked list element
func(this LinkedList) display() {
    if this.head == nil {
        return
    }
    var temp * LinkNode = this.head
    // iterating linked list elements
    for (temp != nil) {
        fmt.Print(" ", temp.data, " →")
        // Visit to next node
        temp = temp.next
    }
    fmt.Print(" NULL\n")
}
func main() {
    var sll * LinkedList = getLinkedList()
    // Add node
    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 class LinkNode
{
    public int data;
    public LinkNode next;
    public LinkNode(int data)
    {
        this.data = data;
        this.next = null;
    }
}
public class LinkedList
{
    public LinkNode head;
    public LinkedList()
    {
        this.head = null;
    }
    // Add node at middle position of linked list
    public void insert(int value)
    {
        // Create a new node
        LinkNode node = new LinkNode(value);
        if (this.head == null)
        {
            this.head = node;
        }
        else
        {
            LinkNode temp = this.head;
            LinkNode middle = this.head;
            // find middle node
            while (temp.next != null && temp.next.next != null)
            {
                temp = temp.next.next;
                middle = middle.next;
            }
            // add node
            node.next = middle.next;
            middle.next = node;
        }
    }
    // Display linked list element
    public void display()
    {
        if (this.head == null)
        {
            return;
        }
        LinkNode temp = this.head;
        // 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)
    {
        LinkedList sll = new LinkedList();
        // Add node
        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
class LinkNode
{
    public $data;
    public $next;
    public  function __construct($data)
    {
        $this->data = $data;
        $this->next = NULL;
    }
}
class LinkedList
{
    public $head;
    public  function __construct()
    {
        $this->head = NULL;
    }
    // Add node at middle position of linked list
    public  function insert($value)
    {
        // Create a new node
        $node = new LinkNode($value);
        if ($this->head == NULL)
        {
            $this->head = $node;
        }
        else
        {
            $temp = $this->head;
            $middle = $this->head;
            // find middle node
            while ($temp->next != NULL && $temp->next->next != NULL)
            {
                $temp = $temp->next->next;
                $middle = $middle->next;
            }
            // add node
            $node->next = $middle->next;
            $middle->next = $node;
        }
    }
    // Display linked list element
    public  function display()
    {
        if ($this->head == NULL)
        {
            return;
        }
        $temp = $this->head;
        // 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();
    // Add node
    $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
class LinkNode
{
    constructor(data)
    {
        this.data = data;
        this.next = null;
    }
}
class LinkedList
{
    constructor()
    {
        this.head = null;
    }
    // Add node at middle position of linked list
    insert(value)
    {
        // Create a new node
        var node = new LinkNode(value);
        if (this.head == null)
        {
            this.head = node;
        }
        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;
            }
            // add node
            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();
    // Add node
    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
class LinkNode :
    def __init__(self, data) :
        self.data = data
        self.next = None
    

class LinkedList :
    def __init__(self) :
        self.head = None
    
    #  Add node at middle position of linked list
    def insert(self, value) :
        #  Create a new node
        node = LinkNode(value)
        if (self.head == None) :
            self.head = node
        else :
            temp = self.head
            middle = self.head
            #  find middle node
            while (temp.next != None and temp.next.next != None) :
                temp = temp.next.next
                middle = middle.next
            
            #  add node
            node.next = middle.next
            middle.next = node
        
    
    #  Display linked list element
    def display(self) :
        if (self.head == None) :
            return
        
        temp = self.head
        #  iterating linked list elements
        while (temp != None) :
            print("", temp.data ,"→", end = "")
            #  Visit to next node
            temp = temp.next
        
        print(" NULL")
    

def main() :
    sll = LinkedList()
    #  Add node
    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
python insert linked list node in middle position
#  Ruby Program for
#  Insert linked list element at middle 

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

end

class LinkedList 
    # Define the accessor and reader of class LinkedList
    attr_reader :head
    attr_accessor :head
    def initialize() 
        self.head = nil
    end

    #  Add node at middle position of linked list
    def insert(value) 
        #  Create a new node
        node = LinkNode.new(value)
        if (self.head == nil) 
            self.head = node
        else
 
            temp = self.head
            middle = self.head
            #  find middle node
            while (temp.next != nil && temp.next.next != nil) 
                temp = temp.next.next
                middle = middle.next
            end

            #  add node
            node.next = middle.next
            middle.next = node
        end

    end

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

        temp = self.head
        #  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 = LinkedList.new()
    #  Add node
    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,
    var next: LinkNode)
{
    def this(data: Int)
    {
        this(data, null);
    }
}
class LinkedList(var head: LinkNode)
{
    def this()
    {
        this(null);
    }
    // Add node at middle position of linked list
    def insert(value: Int): Unit = {
        // Create a new node
        var node: LinkNode = new LinkNode(value);
        if (this.head == null)
        {
            this.head = node;
        }
        else
        {
            var temp: LinkNode = this.head;
            var middle: LinkNode = this.head;
            // find middle node
            while (temp.next != null && temp.next.next != null)
            {
                temp = temp.next.next;
                middle = middle.next;
            }
            // add node
            node.next = middle.next;
            middle.next = node;
        }
    }
    // Display linked list element
    def display(): Unit = {
        if (this.head == null)
        {
            return;
        }
        var temp: LinkNode = this.head;
        // 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 = {
        var sll: LinkedList = new LinkedList();
        // Add node
        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
class LinkNode
{
    var data: Int;
    var next: LinkNode? ;
    init(_ data: Int)
    {
        self.data = data;
        self.next = nil;
    }
}
class LinkedList
{
    var head: LinkNode? ;
    init()
    {
        self.head = nil;
    }
    // Add node at middle position of linked list
    func insert(_ value: Int)
    {
        // Create a new node
        let node: LinkNode = LinkNode(value);
        if (self.head == nil)
        {
            self.head = node;
        }
        else
        {
            var temp: LinkNode? = self.head;
            var middle: LinkNode? = self.head;
            // find middle node
            while (temp!.next  != nil && temp!.next!.next  != nil)
            {
                temp = temp!.next!.next;
                middle = middle!.next;
            }
            // add node
            node.next = middle!.next;
            middle!.next = node;
        }
    }
    // Display linked list element
    func display()
    {
        if (self.head == nil)
        {
            return;
        }
        var temp: LinkNode? = self.head;
        // iterating linked list elements
        while (temp  != nil)
        {
            print("", temp!.data ,"→", terminator: "");
            // Visit to next node
            temp = temp!.next;
        }
        print(" NULL");
    }
}
func main()
{
    let sll: LinkedList = LinkedList();
    // Add node
    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
class LinkNode
{
    var data: Int;
    var next: LinkNode ? ;
    constructor(data: Int)
    {
        this.data = data;
        this.next = null;
    }
}
class LinkedList
{
    var head: LinkNode ? ;
    constructor()
    {
        this.head = null;
    }
    // Add node at middle position of linked list
    fun insert(value: Int): Unit
    {
        // Create a new node
        val node: LinkNode = LinkNode(value);
        if (this.head == null)
        {
            this.head = node;
        }
        else
        {
            var temp: LinkNode ? = this.head;
            var middle: LinkNode ? = this.head;
            // find middle node
            while (temp?.next != null && temp.next?.next != null)
            {
                temp = temp.next?.next;
                middle = middle?.next;
            }
            // add node
            node.next = middle?.next;
            middle?.next = node;
        }
    }
    // Display linked list element
    fun display(): Unit
    {
        if (this.head == null)
        {
            return;
        }
        var temp: LinkNode ? = this.head;
        // 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
{
    val sll: LinkedList = LinkedList();
    // Add node
    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.

New Comment







© 2021, kalkicode.com, All rights reserved