查找链表的中间元素

Question

我们有一个包含“n”个元素的链表。我怎样才能找到中间元素？我可以这样做吗？（这是一个伪代码）Node current = head;for (int i = 0; i < n/2; i++){    current = current.next;}return current;

Answer 1

是的，你的代码是正确的。下面是使用 Tortoise and Hare 算法的另一种方法。

if(head == null) return head;

if(head.next == null || head.next.next == null) return head;

Node slow = head,fast = head.next.next;

while(fast != null && fast.next != null){

    slow = slow.next;

    fast = fast.next.next;

}

if(fast != null) slow = slow.next;

Console.writeLine(slow.data);

如果列表是[1,2,3,4,5,6,7]=> 这将返回4。

如果 list 是[1,2,3,4,5,6]=> 这将返回3.// 如果你愿意你可以4通过轻微的修改返回。

如果 list[1]或[1,2]=> 它1再次返回// 您可以根据需要修改它。

Answer 2

这是一个简化的算法：

var enumerator1 = linked.GetEnumerator();

var enumerator2 = linked.GetEnumerator();

int count = 0;

while (enumerator1.MoveNext())

{

    count++;

    if (count % 2 == 0)

        enumerator2.MoveNext();

}

主指针每移动两次，第二指针就会移动一次。

Answer 3

简单：

var current = list.ElementAt(list.Count()/2);