在链表中循环

是否有线性方法可以找到单链表的中间元素？(线性-意味着你只能在列表中迭代一次，也就是说，你所做的迭代次数总和不能超过列表的长度(

谢谢！

编辑：问题指定您不能事先知道列表的长度。

编辑2：这个问题是为Java编写的，但使用了一些没有length((方法的链表定义

这可能不符合您的限制，但它们非常模糊。它只需要列表的一次迭代(从开始只开始一次，到结束只结束一次(，但它需要存储两个独立的指针(因此，它会跟随列表下一个指针的一半两次(。

使用两个指向列表第一个元素的变量。然后遍历列表，每次迭代时将第一个指针增加1位，将第二个指针增加2位。一旦第二个指针到达列表的末尾，第一个指针将包含中间元素(如果存在(。

一点伪代码。。。

list = [1, 2, 3, 4, 5]
ptr1 = list[0]
ptr2 = list[0]
while ptr2 is not null
    ptr1 = ptr1.next
    ptr2 = ptr2.next.next
return ptr1

Node ptr1 = head; 
Node ptr2 = head;
while(ptr1 != null || ptr1->next != null){
    ptr1 = ptr1 -> next -> next;
    ptr2 = ptr2 -> next; 
}

编辑：

//this is wrong, so not needed so, upper part is enough. 
if(ptr1->next != null){
    ptr2 = ptr2 -> next;
}

Node p1 = head;
Node mid = head;
while(p1 != null){
    p1 = p1.next();
    p1 = p1.next();
    mid = mid.next(); 
}

注意，循环中p1和mid的顺序很重要。举个例子，如果列表中只有一个元素。这意味着头部将位于中间。然而，mid将返回null，因为它进入下一个元素，而不是在进入下一元素之前退出循环。

错误的实施

while(p1 != null){
    mid = mid.next(); // incorrect order.
    p1 = p1.next().next(); //will cause exception if p1.next == null
}

相关内容