如何在不遍历单链表的情况下查找中间节点？

Question

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

首先，这是否可能呢？

在一次遍历中，我使用传统方法使用两个指针，一个跳2个位置，另一个跳1个位置..是否有其他方法可以在一次遍历中找到中间节点呢？

- Arunachalam

---

我认为这是欺骗。虽然只有一个循环，但执行的操作数量却与遍历两次相同。 - Andrey

@Audrey 我完全同意。那个提出这种典型的“聪明”回答的人需要被打一巴掌 :) - Henley

Answer 1

不，这是不可能的。节点的地址是任意的，因此没有办法在不遍历它们的情况下知道它们的地址。

- Oliver Charlesworth

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

- codewarrior

---

这种方法与先解析整个内容，然后通过计数回到中间相比真的更有效吗？步骤数量不是一样的吗？ - endless

Answer 3

是的，如果您控制列表添加和删除的所有方面，则可以。

如果在添加或删除过程中保持对被视为中间节点的引用，则可以完成。必须处理几个情况。此外，还有一些场景需要考虑，例如，如果要考虑偶数个元素，那么中间节点将是什么？等等。

因此，您真正做的不是“查找”中间节点，而是跟踪它。

- Matthew Cox

---

我喜欢这个想法，但是在一半的插入操作中，你仍然需要遍历列表比正常情况下更多的节点。因为当你在中间节点之前添加一个节点时，你可能需要继续查找紧挨着中间节点之前的那个节点。 - Null Set

只有在您只附加/删除头部或尾部节点时，这才有任何益处。如果您进行任意插入/删除，则需要确定您是在中间节点之前还是之后进行操作，这需要遍历。O（n）插入/删除听起来并不像是一个非常有用的链表！ - Oliver Charlesworth

此外，在删除时，您必须重新查找中间位置，因为它是单向链接，无法向后移动。 - Nick Johnson

Answer 4

List list = new LinkedList();
    for (int i = 0; i < 50; i++) {
    list.add(String.valueOf(i));
}

int end = list.size() - 1;
int start = 0;
while (start > end) {
    start++;
    end--;
}
if(start == end) //The arrays length is an odd number and you found the middle
    return start;
else //The arrays length is an even number and there really isn't a middle
    //Do something else here because you have an even number 

我在其他解决方案页面上看到了这段代码... 这不是另一种单向遍历列表的方法吗？

- Andy Khatter

---

单向链表。不能执行 end--。 - Jive Dadson

Answer 5

import java.util.LinkedList;
import java.util.List;


public class consoleApp 
{
    public static void main(String[] args)
    {
        List list = new LinkedList();
        for (int i = 0; i < 50; i++) 
        {
            list.add(String.valueOf(i));
        }

        int end = list.size();

        int start = 0;
        while (start< end) 
        {
            start++;
            end--;
        }

        if(start == end) 
            System.out.println(start);
    }
}

- radheshyam

---

这将给您中间节点的索引，而不是元素。 - Origin

你的例子中：list.get(list.size()/2)足以获得中点，我想是这样的。 - Ashish