遍历链表
遍历链表
提问于 2014-07-18 06:58:13
有没有一种线性的方法来找到单链表的中间元素？(线性-意味着你只能遍历列表一次，总迭代次数不能超过列表的长度)
谢谢!
编辑:问题指定您不能预先知道列表的长度。
编辑2:问题是为Java编写的，但使用了一些没有length()方法的链表定义
回答 4
Stack Overflow用户
发布于 2014-07-18 07:10:16
这可能不符合您的约束，但它们相当模糊。它只需要列表的一次迭代(从开始只开始一次，到达结束只一次)，但它需要在您这样做时存储两个独立的指针(因此跟随列表的一半的下一个指针两次)。
将pointer_1和pointer_2设置为列表中的第一个节点，并将设置为0
- 将pointer_1设置为偶数计数器
- 如果pointer_2为偶数，则将计数器设置为pointer_1 pointer_1不在列表的末尾，goto 2
- 当循环退出时，pointer_2位于列表的中间
Stack Overflow用户
发布于 2014-07-18 07:16:43
使用两个指向列表第一个元素的变量。然后遍历列表，在每次迭代中将第一个指针递增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 ptr1Stack Overflow用户
发布于 2014-07-18 07:45:57
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;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/24814852
复制相关文章
相似问题
腾讯云开发者
