如何在不遍历整个列表的情况下查找链接列表中的中间元素？

Question

如何在不遍历整个列表的情况下在链接列表中查找中间元素.？...并且最多只能使用2个指针......怎么办？....还没有给出列表的长度.

Answer 1

除非你知道长度,否则我没有看到如何在不遍历整个列表的情况下完成它.

我猜测答案是希望一个指针一次遍历一个元素,而第二个指针一次移动2个元素.
这样,当第二个指针到达结尾时,第一个指针将位于中间.

Answer 2

以下代码将帮助您获得中间元素.你需要使用两个指针"快"和"慢".在每一步,快速指针将增加2,慢速将增加1.当列表结束时,慢速指针将位于中间.

让我们考虑一下Node这样的样子

class Node
{
  int data;
  Node next;
}

LinkedList有一个getter方法来提供链表的头部

public Node getHead()
{
  return this.head;
}

下面的方法将获得列表的中间元素(不知道列表的大小)

public int getMiddleElement(LinkedList l)
{
    return getMiddleElement(l.getHead());
}

private int getMiddleElement(Node n)
{
    Node slow = n;
    Node fast = n;

    while(fast!=null && fast.next!=null)
    {
        fast = fast.next.next;
        slow = slow.next;
    }

    return slow.data;
}

示例:
如果列表为1-2-3-4-5,则中间元素为3
如果列表为1-2-3-4,则中间元素为3