如何在没有遍历的情况下在单链表中找到中间节点？

Question

如何在没有遍历的情况下在单链表中找到中间节点？

它有可能在第一位吗？

在一次遍历中我使用传统方法使用2个指针,一个跳跃的2个位置,另一个跳跃的一个位置..是否有任何其他方法在一次遍历中找到中间节点

Answer 1

不,这是不可能的.节点的地址是任意的,所以没有遍历它们就无法知道它们.

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