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.

Before Delete Middle node

After Delete Middle node

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
    Delete 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 beginning 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 = sll->head;
    }
    sll->head = 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)
    {
        // Display node value
        printf(" %d →", temp->data);
        // Visit to next node
        temp = temp->next;
    }
    printf(" NULL\n");
}
// Delete the middle node of linked list
void deleteMid(struct LinkNode *head)
{
    if (head == NULL)
    {
        // When linked list are no elements
        printf("\nEmpty Linked List\n");
    }
    else if (head->next == NULL && 
             head->next->next == NULL)
    {
        // When linked list are less than  of 3 nodes
        printf("\nLess then 3 node of linked list\n");
    }
    else
    {
        struct LinkNode *temp = head;
        struct LinkNode *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
        printf("Delete node : %d\n", temp->data);
        // Change link
        midPrevious->next = temp->next;
        free(temp);
    }
}
int main(int argc, char
    const *argv[])
{
    struct SingleLL *sll = newLinkedList();
    // Linked list
    // 7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
    addNode(sll,1);
    addNode(sll,2);
    addNode(sll,3);
    addNode(sll,4);
    addNode(sll,5);
    addNode(sll,6);
    addNode(sll,7);
    printf(" Linked List \n");
    display(sll->head);
    printf("Before Delete middle node\n");
    display(sll->head);
  
    deleteMid(sll->head);
    printf("After Delete middle node\n");
    display(sll->head);
    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
*/
// Linked list node
class LinkNode
{
    public int data;
    public LinkNode next;
    public LinkNode(int data)
    {
        this.data = data;
        this.next = null;
    }
}
public class SingleLL
{
    public LinkNode head;
    public SingleLL()
    {
        this.head = null;
    }
    // Adding new node at beginning of linked list
    public void addNode(int data)
    {
        // Create new node
        LinkNode node = new LinkNode(data);
        // Connect current node to previous head
        node.next = this.head;
        this.head = node;
    }
    // Display linked list element
    public void display()
    {
        if (this.head == null)
        {
            return;
        }
        LinkNode temp = this.head;
        // iterating linked list elements
        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()
    {
        if (this.head == null)
        {
            // When linked list are no elements
            System.out.println("Empty Linked List");
        }
        else if (this.head.next == null && 
                 this.head.next.next == null)
        {
            // When linked list are less than  of 3 nodes
            System.out.println("Less then 3 node of linked list");
        }
        else
        {
            LinkNode temp = this.head;
            LinkNode 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
            System.out.println("Delete node : " + temp.data);
            // Change link
            midPrevious.next = temp.next;
        }
    }
    public static void main(String[] args)
    {
        SingleLL sll = new SingleLL();
        // Linked list
        // 7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
        sll.addNode(1);
        sll.addNode(2);
        sll.addNode(3);
        sll.addNode(4);
        sll.addNode(5);
        sll.addNode(6);
        sll.addNode(7);
        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
*/
// Linked list node
class LinkNode
{
    public: int data;
    LinkNode *next;
    LinkNode(int data)
    {
        this->data = data;
        this->next = NULL;
    }
};
class SingleLL
{
    public: LinkNode *head;
    SingleLL()
    {
        this->head = NULL;
    }
    // Adding new node at beginning of linked list
    void addNode(int data)
    {
        // Create new node
        LinkNode *node = new LinkNode(data);
        // Connect current node to previous head
        node->next = this->head;
        this->head = node;
    }
    // Display linked list element
    void display()
    {
        if (this->head == NULL)
        {
            return;
        }
        LinkNode *temp = this->head;
        // iterating linked list elements
        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()
    {
        if (this->head == NULL)
        {
            // When linked list are no elements
            cout << "Empty Linked List" << endl;
        }
        else if (this->head->next == NULL && 
                 this->head->next->next == NULL)
        {
            // When linked list are less than  of 3 nodes
            cout << "Less then 3 node of linked list" << endl;
        }
        else
        {
            LinkNode *temp = this->head;
            LinkNode *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
            cout << "Delete node : " << temp->data << endl;
            // Change link
            midPrevious->next = temp->next;
            
            delete temp;
        }
    }
};
int main()
{
    SingleLL *sll = new SingleLL();
    // Linked list
    // 7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
    sll->addNode(1);
    sll->addNode(2);
    sll->addNode(3);
    sll->addNode(4);
    sll->addNode(5);
    sll->addNode(6);
    sll->addNode(7);
    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
*/
// 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 SingleLL struct {
    head * LinkNode
}
func getSingleLL() * SingleLL {
    var me *SingleLL = &SingleLL {}
    me.head = nil
    return me
}
// Adding new node at beginning of linked list
func(this *SingleLL) addNode(data int) {
    // Create new node
    var node * LinkNode = getLinkNode(data)
    // Connect current node to previous head
    node.next = this.head
    this.head = node
}
// Display linked list element
func(this SingleLL) display() {
    if this.head == nil {
        return
    }
    var temp * LinkNode = this.head
    // iterating linked list elements
    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() {
    if this.head == nil {
        // When linked list are no elements
        fmt.Println("Empty Linked List")
    } else if this.head.next == nil && 
              this.head.next.next == nil {
        // When linked list are less than  of 3 nodes
        fmt.Println("Less then 3 node of linked list")
    } else {
        var temp * LinkNode = this.head
        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)
        // Change link
        midPrevious.next = temp.next
    }
}
func main() {
    var sll * SingleLL = getSingleLL()
    // Linked list
    // 7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
    sll.addNode(1)
    sll.addNode(2)
    sll.addNode(3)
    sll.addNode(4)
    sll.addNode(5)
    sll.addNode(6)
    sll.addNode(7)
    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
*/
// Linked list node
public class LinkNode
{
    public int data;
    public LinkNode next;
    public LinkNode(int data)
    {
        this.data = data;
        this.next = null;
    }
}
public class SingleLL
{
    public LinkNode head;
    public SingleLL()
    {
        this.head = null;
    }
    // Adding new node at beginning of linked list
    public void addNode(int data)
    {
        // Create new node
        LinkNode node = new LinkNode(data);
        // Connect current node to previous head
        node.next = this.head;
        this.head = node;
    }
    // Display linked list element
    public void display()
    {
        if (this.head == null)
        {
            return;
        }
        LinkNode temp = this.head;
        // iterating linked list elements
        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()
    {
        if (this.head == null)
        {
            // When linked list are no elements
            Console.WriteLine("Empty Linked List");
        }
        else if (this.head.next == null && this.head.next.next == null)
        {
            // When linked list are less than  of 3 nodes
            Console.WriteLine("Less then 3 node of linked list");
        }
        else
        {
            LinkNode temp = this.head;
            LinkNode 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.WriteLine("Delete node : " + temp.data);
            // Change link
            midPrevious.next = temp.next;
        }
    }
    public static void Main(String[] args)
    {
        SingleLL sll = new SingleLL();
        // Linked list
        // 7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
        sll.addNode(1);
        sll.addNode(2);
        sll.addNode(3);
        sll.addNode(4);
        sll.addNode(5);
        sll.addNode(6);
        sll.addNode(7);
        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
*/
// Linked list node
class LinkNode
{
    public $data;
    public $next;
    public  function __construct($data)
    {
        $this->data = $data;
        $this->next = NULL;
    }
}
class SingleLL
{
    public $head;
    public  function __construct()
    {
        $this->head = NULL;
    }
    // Adding new node at beginning of linked list
    public  function addNode($data)
    {
        // Create new node
        $node = new LinkNode($data);
        // Connect current node to previous head
        $node->next = $this->head;
        $this->head = $node;
    }
    // Display linked list element
    public  function display()
    {
        if ($this->head == NULL)
        {
            return;
        }
        $temp = $this->head;
        // iterating linked list elements
        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()
    {
        if ($this->head == NULL)
        {
            // When linked list are no elements
            echo("Empty Linked List".
                "\n");
        }
        else if ($this->head->next == NULL && $this->head->next->next == NULL)
        {
            // When linked list are less than  of 3 nodes
            echo("Less then 3 node of linked list".
                "\n");
        }
        else
        {
            $temp = $this->head;
            $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");
            // Change link
            $midPrevious->next = $temp->next;
        }
    }
}

function main()
{
    $sll = new SingleLL();
    // Linked list
    // 7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
    $sll->addNode(1);
    $sll->addNode(2);
    $sll->addNode(3);
    $sll->addNode(4);
    $sll->addNode(5);
    $sll->addNode(6);
    $sll->addNode(7);
    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
*/
// Linked list node
class LinkNode
{
    constructor(data)
    {
        this.data = data;
        this.next = null;
    }
}
class SingleLL
{
    constructor()
    {
        this.head = null;
    }
    // Adding new node at beginning of linked list
    addNode(data)
    {
        // Create new node
        var node = new LinkNode(data);
        // Connect current node to previous head
        node.next = this.head;
        this.head = node;
    }
    // Display linked list element
    display()
    {
        if (this.head == null)
        {
            return;
        }
        var temp = this.head;
        // iterating linked list elements
        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()
    {
        if (this.head == null)
        {
            // When linked list are no elements
            console.log("Empty Linked List");
        }
        else if (this.head.next == null && 
                 this.head.next.next == null)
        {
            // When linked list are less than  of 3 nodes
            console.log("Less then 3 node of linked list");
        }
        else
        {
            var temp = this.head;
            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);
            // Change link
            midPrevious.next = temp.next;
        }
    }
}

function main()
{
    var sll = new SingleLL();
    // Linked list
    // 7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
    sll.addNode(1);
    sll.addNode(2);
    sll.addNode(3);
    sll.addNode(4);
    sll.addNode(5);
    sll.addNode(6);
    sll.addNode(7);
    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

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

class SingleLL :
    def __init__(self) :
        self.head = None
    
    #  Adding new node at beginning of linked list
    def addNode(self, data) :
        #  Create new node
        node = LinkNode(data)
        #  Connect current node to previous head
        node.next = self.head
        self.head = node
    
    #  Display linked list element
    def display(self) :
        if (self.head == None) :
            return
        
        temp = self.head
        #  iterating linked list elements
        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) :
        if (self.head == None) :
            #  When linked list are no elements
            print("Empty Linked List")
        elif (self.head.next == None and self.head.next.next == None) :
            #  When linked list are less than  of 3 nodes
            print("Less then 3 node of linked list")
        else :
            temp = self.head
            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)
            #  Change link
            midPrevious.next = temp.next
        
    

def main() :
    sll = SingleLL()
    #  Linked list
    #  7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
    sll.addNode(1)
    sll.addNode(2)
    sll.addNode(3)
    sll.addNode(4)
    sll.addNode(5)
    sll.addNode(6)
    sll.addNode(7)
    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

#  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 SingleLL 
    # Define the accessor and reader of class SingleLL
    attr_reader :head
    attr_accessor :head
    def initialize() 
        self.head = nil
    end

    #  Adding new node at beginning of linked list
    def addNode(data) 
        #  Create new node
        node = LinkNode.new(data)
        #  Connect current node to previous head
        node.next = self.head
        self.head = node
    end

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

        temp = self.head
        #  iterating linked list elements
        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() 
        if (self.head == nil) 
            #  When linked list are no elements
            print("Empty Linked List", "\n")
        elsif (self.head.next == nil && self.head.next.next == nil) 
            #  When linked list are less than  of 3 nodes
            print("Less then 3 node of linked list", "\n")
        else
 
            temp = self.head
            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")
            #  Change link
            midPrevious.next = temp.next
        end

    end

end

def main() 
    sll = SingleLL.new()
    #  Linked list
    #  7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
    sll.addNode(1)
    sll.addNode(2)
    sll.addNode(3)
    sll.addNode(4)
    sll.addNode(5)
    sll.addNode(6)
    sll.addNode(7)
    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
*/
// Linked list node
class LinkNode(var data: Int,
    var next: LinkNode)
{
    def this(data: Int)
    {
        this(data, null);
    }
}
class SingleLL(var head: LinkNode)
{
    def this()
    {
        this(null);
    }
    // Adding new node at beginning of linked list
    def addNode(data: Int): Unit = {
        // Create new node
        var node: LinkNode = new LinkNode(data);
        // Connect current node to previous head
        node.next = this.head;
        this.head = 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)
        {
            // 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 = {
        if (this.head == null)
        {
            // When linked list are no elements
            println("Empty Linked List");
        }
        else if (this.head.next == null && 
                 this.head.next.next == null)
        {
            // When linked list are less than  of 3 nodes
            println("Less then 3 node of linked list");
        }
        else
        {
            var temp: LinkNode = this.head;
            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);
            // Change link
            midPrevious.next = temp.next;
        }
    }
}
object Main
{
    def main(args: Array[String]): Unit = {
        var sll: SingleLL = new SingleLL();
        // Linked list
        // 7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
        sll.addNode(1);
        sll.addNode(2);
        sll.addNode(3);
        sll.addNode(4);
        sll.addNode(5);
        sll.addNode(6);
        sll.addNode(7);
        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
*/
// Linked list node
class LinkNode
{
    var data: Int;
    var next: LinkNode? ;
    init(_ data: Int)
    {
        self.data = data;
        self.next = nil;
    }
}
class SingleLL
{
    var head: LinkNode? ;
    init()
    {
        self.head = nil;
    }
    // Adding new node at beginning of linked list
    func addNode(_ data: Int)
    {
        // Create new node
        let node: LinkNode = LinkNode(data);
        // Connect current node to previous head
        node.next = self.head;
        self.head = node;
    }
    // Display linked list element
    func display()
    {
        if (self.head == nil)
        {
            return;
        }
        var temp: LinkNode? = self.head;
        // iterating linked list elements
        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()
    {
        if (self.head == nil)
        {
            // When linked list are no elements
            print("Empty Linked List");
        }
        else if (self.head!.next == nil && 
                 self.head!.next!.next == nil)
        {
            // When linked list are less than  of 3 nodes
            print("Less then 3 node of linked list");
        }
        else
        {
            var temp: LinkNode? = self.head;
            var midPrevious: LinkNode? = 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;
                }
                // 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);
            // Change link
            midPrevious!.next = temp!.next;
        }
    }
}
func main()
{
    let sll: SingleLL = SingleLL();
    // Linked list
    // 7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
    sll.addNode(1);
    sll.addNode(2);
    sll.addNode(3);
    sll.addNode(4);
    sll.addNode(5);
    sll.addNode(6);
    sll.addNode(7);
    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
*/
// Linked list node
class LinkNode
{
    var data: Int;
    var next: LinkNode ? ;
    constructor(data: Int)
    {
        this.data = data;
        this.next = null;
    }
}
class SingleLL
{
    var head: LinkNode ? ;
    constructor()
    {
        this.head = null;
    }
    // Adding new node at beginning of linked list
    fun addNode(data: Int): Unit
    {
        // Create new node
        val node: LinkNode = LinkNode(data);
        // Connect current node to previous head
        node.next = this.head;
        this.head = 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)
        {
            // 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
    {
        if (this.head == null)
        {
            // When linked list are no elements
            println("Empty Linked List");
        }
        else if (this.head?.next == null && this.head?.next?.next == null)
        {
            // When linked list are less than  of 3 nodes
            println("Less then 3 node of linked list");
        }
        else
        {
            var temp: LinkNode ? = this.head;
            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);
            // Change link
            midPrevious?.next = temp.next;
        }
    }
}
fun main(args: Array < String > ): Unit
{
    val sll: SingleLL = SingleLL();
    // Linked list
    // 7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL
    sll.addNode(1);
    sll.addNode(2);
    sll.addNode(3);
    sll.addNode(4);
    sll.addNode(5);
    sll.addNode(6);
    sll.addNode(7);
    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.

New Comment







© 2021, kalkicode.com, All rights reserved