java - 如何在一次迭代中到达单向链表的中间？

Question

最近有人问我一个问题，在单向链表中我们如何在一次迭代中到达链表的中间。

A --> B --> C --> D (even nodes)

为此它应该返回指向 B 的地址

A --> B --> C (odd nodes)

为此它也应该返回指向 B 的地址

有一种解决方案是采用两个指针，一个移动一次，另一个移动两次，但它在这里似乎不起作用

LinkedList p1,p2;

while(p2.next != null)
{
    p1 = p1.next;
    p2 = p2.next.next;

}

System.out.print("middle of the node" + p1.data); //This does not give accurate result in odd and even

如果有人以前这样做过，请帮忙。

Answer 1

基本算法是

0取两个指针

1 使两者都指向第一个节点

2 首先增加两个节点，如果成功则首先遍历第二个节点到前面的一个节点

3 当第二个到达终点时，第一个到达中间。

更新:

它肯定会在奇数情况下工作，对于即使是您需要检查一个条件，如果允许第一个点移动下一个但不是下一个next 那么两个指针都将在中间，你需要决定将哪个指针作为中间