如何在一次迭代中走到奇异链表的中间？

最近我被问到一个问题，在一个单独的链表中，我们如何在一次迭代中进入列表的中间位置。

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

除非您成功提升p2两次，否则无法前进p1; 否则，如果列表长度为2，则最终两者都指向末尾（并且您指示甚至长度列表应该朝向开头舍入）。

所以：

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

Answer 2

基本算法是

0拿两个指针

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

2首先使用两个节点递增，如果成功，则首先递增，然后在第二个节点前面遍历一个节点

3当第二个到达结束时，第一个将在中间。

更新：

它肯定会在奇怪的情况下工作，因为即使你需要再检查一个条件，如果第一个点允许下一个移动而不是下一个接下来，那么两个指针都将位于中间你需要决定采取什么作为中间

Answer 3

我知道你已经接受了答案，但这整个问题听起来像是一种聪明的练习，而不是试图获得正确的解决方案。 当你能在O（n / 2）中做到时，为什么要在O（n）中做某事？

编辑：这用于断言O（1）性能，这是不正确的。 感谢ysth指出这一点。

在实践中，您将在零迭代中执行此操作：

 LinkedList list = ... int size = list.size(); int middle = (size / 2) + (size % 2 == 0 ? 0 : 1) - 1; //index of middle item Object o = list.get(middle); //or ListIterator it = list.listIterator(middle); 

Answer 4

采取两个指针和一个移动一半的速率的解决方案应该工作正常。 最有可能的不是解决方案，而是您的实际实施问题。 发布有关实施的更多详细信息。

Answer 5

 static ListElement findMiddle(ListElement head){ ListElement slower = head; ListElement faster = head; while(faster.next != null && faster.next.next !=null ){ faster = faster.next.next; slower = slower.next; } return slower; } 

Answer 6

 public static Node middle(Node head){ Node slow=head,fast=head; while(fast!=null& fast.next!=null && fast.next.next!=null){ slow=slow.next; fast=fast.next.next; } if(fast!=null && fast.next!=null){ slow=slow.next; } return slow; }