Home » Algorithm » Datastructure » Interviews » Linked List » Delete Middle Node of Linked List in Java

Delete Middle Node of Linked List in Java

in , , , - on 04:13:00 - No comments

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;
        }
    }

}

Categories: , , ,

Post a Comment