Delete Middle Node of Linked List in Java

Delete Middle Node of Linked List in Java.

---

Given a linked list, Delete the middle node of linked list.

Lets see sample input and output for better understanding:

Algorithm 

---

We will use tortoise and hare pointer to find the middle of the linked list, we will also keep track of just previous node of middle node.

when the hare pointer reaches null, tortoise would be pointing to middle node and previous to middle node would be tracked by previousNode.

just set previousNode.next = tortoise.next will solve our problem.

Java Program to Delete Middle Node of Linked List in Java.

---

package com.javabypatel.linkedlist;

/*

Input = 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> 70 -> null
Output: 10 -> 20 -> 30 -> 50 -> 60 -> 70 -> null

Input = 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> null
Output: 10 -> 20 -> 30 -> 50 -> 60 -> null

Input = 10 -> null
Output: null

 */
public class DeleteMiddleNodeOfLinkedList {

    LinkedListNode startNode;

    public static void main(String[] args) {
        new DeleteMiddleNodeOfLinkedList();
    }

    public DeleteMiddleNodeOfLinkedList() {

        addNode(new LinkedListNode(10));
        addNode(new LinkedListNode(20));
        addNode(new LinkedListNode(30));
        addNode(new LinkedListNode(40));
        addNode(new LinkedListNode(50));
        addNode(new LinkedListNode(60));
        addNode(new LinkedListNode(70));

        printLinkList();

        startNode = deleteMiddleNode(startNode);

        printLinkList();
    }

    private LinkedListNode deleteMiddleNode(LinkedListNode startNode) {
        if (startNode == null || startNode.getNext() == null) {
            return null;
        }
        LinkedListNode tortoise = startNode;
        LinkedListNode hare = startNode;
        LinkedListNode previousOfTortoise = null;

        while (hare != null && hare.getNext() != null) {
            previousOfTortoise = tortoise;
            tortoise = tortoise.getNext();
            hare = hare.getNext().getNext();
        }
        previousOfTortoise.setNext(tortoise.getNext());
        return startNode;
    }

    private void printLinkList() {
        LinkedListNode tempNode1 = startNode;
        while (tempNode1 != null) {
            System.out.print(tempNode1.getData() + " ");
            tempNode1 = tempNode1.getNext();
        }
        System.out.println();
    }

    private void addNode(LinkedListNode node) {
        if (startNode != null) {
            LinkedListNode tempNode1 = startNode;
            while (tempNode1.getNext() != null) {
                tempNode1 = tempNode1.getNext();
            }
            tempNode1.setNext(node);
        } else {
            this.startNode = node;
        }
    }

}

You may also like to see

---

Sort Linked list using Merge sort

Bubble Sort

Heap Sort

Selection Sort

Insertion Sort

---

How ConcurrentHashMap works and ConcurrentHashMap interview questions

How Much Water Can A Bar Graph with different heights can Hold

Interview Questions-Answer Bank

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.