Delete middle of linked list

Problem: For any given linked list, delete middle of the linked list

Problem Explanation: For any linked list,

Input: 1 -> 2 ->3 ->4 -> 5

Ouput: 1 -> 2  ->4 -> 5

 

Input: 9 -> 10 ->11 ->12

Ouput: 9 ->11 ->12

Java Implementation

public class DeleteMiddleLL {
    public Node deleteMiddleLL(Node node) {
        if (node == null) {
            return null;
        }
        if (node.getLink() == null) {
            return null;
        }

        Node first = node, second = node, prev = null;
        while (second.getLink() != null && second.getLink().getLink() != null) {
            prev = first;
            first = first.getLink();
            second = second.getLink().getLink();
        }

        if (prev != null) {
            prev.setLink(first.getLink());
            first.setLink(null);
        }

        return node;
    }

    public void printLL(Node node) {
        if (node == null) {
            System.out.println("Linked list is empty");
        }
        while (node != null) {
            System.out.println(node.getValue());
            node = node.getLink();
        }
    }

    public static void main(String[] args) {
        Node node = new Node(1, null);
        node.setLink(new Node(2, null));
        node.getLink().setLink(new Node(3, null));
        node.getLink().getLink().setLink(new Node(4, null));
        node.getLink().getLink().getLink().setLink(new Node(5, null));

        DeleteMiddleLL deleteMiddleLL = new DeleteMiddleLL();

        node = deleteMiddleLL.deleteMiddleLL(node);
        deleteMiddleLL.printLL(node);

    }
}

public class Node {
    int value;
    Node link;

    public Node(int value, Node link) {
        this.value = value;
        this.link = link;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Node getLink() {
        return link;
    }

    public void setLink(Node link) {
        this.link = link;
    }
}

TimeComplexity: O(n)

Note: If you find any other better way to approach to this problem or you find any issue/error in above code snippets/approaches – please share it in the comments section below and get a chance to enrol free of cost for an online Live Data Structure and Algorithm course (specially designed for interview preparation for software companies like Amazon, Google, Facebook, FlipKart, SnapDeal, HealthKart…)