how to find middle node in singly linked list without traversal?

Question

how to find middle node in singly linked list without traversal ?

is it possible in first place ?

In One traversal I Use the traditional method of using 2 pointers one which jump's 2 positions and other which jump's one position ..is there any other approach to find middle node in one traversal

Answer 1

No, it's not possible. The addresses of the nodes are arbitrary, so there's no way of knowing them without traversing them.

Answer 2

public void findMiddleNode() {
    Node n1 = headNode;
    Node n2 = headNode;
    while(n2.getNext() != null && n2.getNext().getNext()!= null) {
        n1 = n1.getNext();
        n2 = n2.getNext().getNext();
    }

    System.out.println("middle node is "+n1.getKey());
}